There’s an active bug related to custom post types and permalinks in WordPress 3.0.3. Here are the conditions that it exists under:

1. Permalinks include %postname%
2. A custom post type exists with an empty value for the slug key on the rewrite array
3. A post/page/etc has been saved after the custom post type was installed

You’ll start getting 404 errors for your content. You can work around it by setting a value for the slug:

replace
'rewrite' => array( 'slug' => '', 'with_front' => false )

with
'rewrite' => array( 'slug' => 'foo', 'with_front' => false )