This is a relatively new problem to me.
I used this plugin for a while, but only recently I reported a large number of 404 errors for attachment pages.
I don't know if it started after a plugin update (not 1.4.13 anyway, maybe one or two updates before), but most likely it started after I checked the "Redirect to the URL of the post attachments parent" option.
Also, in the sitemap I checked the option "media" to exclude this post type, and in fact the map isn't created, but google webmaster tool gives sitemap as the source of not found url http://mysite.com/attachment/
Do I have to include the media post type in the sitemap then?
I tried to update the SEO and WP permalink pages, and I have included in the robots.txt Disallow: /attachment/ but the pages are still
scanned and gives a 404, so it seems that the redirect doesn't work at all.
I haven't tried to select "noindex" under "media" in Titles & Meta because I doubt that it's the right thing to do.