I had this problem too... It was htaccess related.
I did not figure out how to confirm that my .htaccess files were being loaded. Reading up on the Apache docs, it says that using .htaccess should be avoided. My server had them (.htaccess files) disabled. (Running my own apache server here.)
Rather than put the directives in the .htaccess file, I put them into my httpd conf file. Now my (non-default) permalinks work for multisite, and I get better performance too.
(Okay, I am just echoing the performance thing from the Apache docs. I have no idea what the performance difference is.)
For me, I edited /etc/httpd/conf.d/website.conf and inserted at the top:
RewriteRule ^index\.php$ - [L]
and it started working.