Did you go to Admin -> Settings -> Permalinks after setting up the post type? The permalink structure hasn’t been added until you’ve done that. It could be the cause of your problem.
The permalinks page fires $wp_rewrite->flush_rules(); each time the page is visited, so it’s not even necessary to save.