Why can I not view image attachment pages?

It could still be your permalink settings, going to the Settings -> Permalink page and Saving will actually flush the rewrite rules and may just fix the problem. You can also try changing to the default structure and back again if this doesn't work, as I think this rewrites your .htaccess file.

After that you may want to check your .htaccess and make sure it is not corrupted, security and caching plugins can sometimes do this, but this sounds unlikely if everything else is still working fine. Beyond that you still may have your theme or plugin may be interfering somehow.

Your theme will require either a catch all 'attachment.php' template or specific template for the attachment type, ie 'image.php'

here's a very simple one:

image.php

<?php 
get_header();
while ( have_posts() ) : the_post();
the_title( '<h1 class="entry-title">', '</h1>' );
the_content();
endwhile;
get_footer();
?>

From what you've described, it sounds like the theme doesn't have an attachment.php template to handling displaying the actual attachment page.

You check on the attachment page, by going to Appearance->Editor, and checking for an attachment.php; however, I believe that answer is incorrect. WordPress should default to displaying the image on the normal blog index page, if I'm not mistaken. Which means the error could have something to do with a custom permalink structure.

Have you changed the permalink structure? If so, try changing it back to default and see if you still get a 404.