Custom post type permalinks breaking due to 3.1 bug fix

To avoid this from happening simply add flush_rewrite_rules( false ); after your register_post_type function.
you can read about it more here
http://en.bainternet.info/2011/custom-post-type-getting-404-on-permalinks