If accessing a single post gives a 404 error, then the error is most likely in the permalink structure. See the following instructions to fix the error.
In WordPress 2.5, sign in as an administrator and go to the Settings section and then Permalinks. Check the permalink structure in the custom section. The permalink structure should start with the following:
If the custom code starts with something else, change it to this. Making this change should allow the linking to work properly and should remove any 404 errors.
I had this problem when upgrading from version 2.3 to 2.5 and this was the fix.