Category problem when changing permalinks structure

Hello,

I have looked in the WordPress Codex pages and in a lot of other forum posts and couldn’t find any answer…

When I try to switch the permalink structure to something prettier (for example, /year/month/date/post-title.php), the permalinks to posts work fine. Problem is, the links to categories seem to work, except that they all say that “There is no post in this category”.

How can I solve that?