pretty permalinks not working on new MS install

I've just joined WPMU and successfully installed everything including enabling the network. But I can immediately notice that changing the default permalinks to a more user-friendly one (month/name) causes all links on the homepage of the main site to break with 404 errors.

I've seen this issue discussed on the forum and the web (with a lot of user angst) in the last 1-2 years but there seems to be no clear resolution. Does anybody have a fresh and hopefully simple solution to this problem?

I've installed absolutely no plugins or themes to the multi-site installation. My htaccess for reference:

AddHandler php-legacy .php
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]

# uploaded files
RewriteRule ^([_0-9a-zA-Z-]+/)?files/(.+) wp-includes/ms-files.php?file=$2 [L]

# add a trailing slash to /wp-admin
RewriteRule ^([_0-9a-zA-Z-]+/)?wp-admin$ $1wp-admin/ [R=301,L]

RewriteCond %{REQUEST_FILENAME} -f [OR]
RewriteCond %{REQUEST_FILENAME} -d
RewriteRule ^ - [L]
RewriteRule ^[_0-9a-zA-Z-]+/(wp-(content|admin|includes).*) $1 [L]
RewriteRule ^[_0-9a-zA-Z-]+/(.*\.php)$ $1 [L]
RewriteRule . index.php [L]

I'd really like to get this resolved before I build out my site with those ugly default permalinks!