Just wanted to share my recent experience with this issue and how i resolved it in the end after a lot of digging.
Apache self-hosted virtual server
WP 3.4.1 (Multisite setup with subfolders)
I installed a fresh install of WP (3.4.1) and then followed the instructions to upgrade it to multisite. Having followed these to a 'T' (inc wp-config & .htaccess updates and checking mod_rewrite is enabled in php) I found other than the main site page i got 404 errors on any posts and all networked site pages.
Turns out, the clue was I was getting 404 errors on the main site post pages, which points to the .htaccess rewrite rules not being used. After checking this out, you have to make sure that in your Apache httpd.conf file (often located here on servers: /etc/httpd/conf/httpd.conf) you set 'AllowOveride' to 'All' from 'None' which is often the default installed value. This then lets the .htaccess file do its thing, and this fixed the issues for me.
I hope that helps someone! :)