I'm having this problem when testing themes with WordPress' own test data.
The blog has permalinks turned on. One of the test posts has no title. When you are in the post before the no-title post and click on the "Previous Post" link, you get a 404 error. Is this a WP bug? It's driving me nuts.
I'm assuming that the problem could be resolved by creating a permalink regardless of not having a title, but this is not very friendly to users who are "technically challenged."
Your help / comments are appreciated.