404’s on post permalinks could be due to a number of different issues, but for me it was caused by a plugin gone bad during a WordPress update: Top Level Categories was broken by WordPress 3.1, and replacing it with FV Top Level Categories was the fix.