WordPress is having some issues with custom post types. I know this is not just a problem in my local machine as I ran in two places, locally, which is wamp and on a web server. Basically it was a theme I was making, which needed custom posts. The first one I created was fine, the second one started to throw 404's. After some Googling, I found out it was a permalink issue, so I had to use flush_rewrite_rules.
I think this is a moderately serious bug and shouldn't be taken too lightly. I don't use the forums much, so I donno if this is the right place to say this, sorry if its not.