Make sure that your .htaccess file is in your blog’s root directory and has correct permissions. That way when you switch from default permalinks to pretty permalinks then WP can add the correct “re-write rules” to it. Find a great plugin named “AskApache RewriteRules Viewer 3.0” and install it. Let’s you see what your .htaccess file is doing and what rules are really there.
If you are already on pretty permalinks then switch back to default and then pretty again to make sure the rules get written correctly.