Permalink structure doesn't change

Hi all,

I’ve created a multisite network, using sub-domains and the domain mapping plugin. Everything works nice (http://lauretum.net/ and http://lauretum.org both live there) EXCEPT changing the permalink structure.

Changing the permalink structure seems to work within WordPress – it updates without errors and the links in the menu’s change from /?p=123 to /page-title but clicking those links generates error: “The requested URL /sample-page/ was not found on this server.”

I assume there is an issue with the .htaccess file, but I don’t know what. The file is writable by the server and contains:

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

# uploaded files
RewriteRule ^files/(.+) wp-includes/ms-files.php?file=$1 [L]

RewriteCond %{REQUEST_FILENAME} -f [OR]
RewriteCond %{REQUEST_FILENAME} -d
RewriteRule ^ - [L]
RewriteRule . index.php [L]

Any suggestions? Also, I’m lost as where WordPress stores the permalink infomation for other (sub-)domains.