This could be a plugin compatibility problem. Have you tried to disable all plugins and see if that solves the problem?
I found this which may also be of help:
http://dre.im/if-pages-return-a-404-after-wordpress-3-1-upgrade/
- Log in to wp-admin and go to permalinks, click save (this should refresh your permalinks).
- Check to see if this fixes your permalinks. If not, set to default.
- Disable your plugins to remove them out of the equation.
- Log into your server via sFTP/SSH/FTP and find your .htaccess file. It should be located in the root of your WordPress install.
- Pull the htaccess file down so that you have a local back up. Once you’ve pulled it down, go ahead and delete it from your server.
- Go back to wp-admin and visit your permalinks page. try enabling custom permalinks.
This should remedy the issue and you can go ahead and reenable your plugins.