This happened after the recent update to WordPress 2.8.5 at a site I operate for my wife. http://wedding-cafe.co.nz
There are 10 categories on the site. All of the category pages can be viewed except two: dresses and advice. They give 404 errors.
The tag pages for the same two words are also missing in action - but other tag pages can display normally.
I only noticed the missing category pages when they were flagged by Google Webmaster Tools