not quite sure why but when using version 1.05 of the plugin everything on my site works great.
I upgrade to sitemaps 1.1.5 and I keep getting 404 not found on my custom post types postings.
I remove the latest version and reinstall 1.0.5 and everything is OK again.
Not sure why your sitemap plugin should impact (presumably) the permalink structure of custom post types.
Still as long as the latest update is not a security update I'm happy to stay on the old version of this great plugin.