I have posted about the same subject quite some time ago. It was solved, but came back after upgrading from 2.6.1 to 2.6.2.
When I choose a category from the category widget dropdown, not the "pretty permalink" is displayed, but what looks like a default permalink and it doesn't work (the page reloads). When I "manage" "permalinks" to default and back to custom, the dropdown works for a short while only to return to the problem a little later. When I don't use the dropdown, there is no problem.
Any ideas?