The default permalink naming scheme used by WordPress is bad.  Most people wind up changing it and most documentation on the subject of changing permalinks centers around redirecting the old links to the new ones so you don't erase all your hard-earned credibility.

This post is about a totally different issue when changing permalinks.  A very few people will change their permalink structure and then find that every link clicked on the WordPress site results in a 404.  This has nothing to do with migration or redirection–even links to posts made after the permalink change will 404.

The problem is in the apache configuration.  If you're getting 404's, here's how to fix it:  First of all, WordPress relies on mod_rewrite for non-default permalinks, so make sure that module is loaded.  Second, there's a .htaccess file with the rewrite rules that needs to be able to take effect, so check the httpd.conf file section for your WordPress directory and try adding

AllowOverride All

And that should fix it.