mod_rewrite not working with serveralias

Question

TL;DR:

Apache is not processing urls for server aliases.

Details:

I am trying to set up a wordpress multisite (a feature of wordpress 3.+ which allows to host multiple blogs at once). The main domain is yeloblog.com Then I want to map domains to the sub-blogs. In other words, I want xananax.com to serve xananax.yeloblog.com.
Things is, permalinks (this is how wordpress calls SEO-friendly urls) don't work in mapped domains. I spend days trying to fix wordpress, until I replaced the index.php file with the following:

<?php
echo '<pre>';
echo 'Server Name: '.$_SERVER['SERVER_NAME']."\n";
echo 'Request URI: '.$_SERVER['REQUEST_URI']."\n";
echo 'Redirect URL: '. $_SERVER['REDIRECT_URL']."\n";
print_r($_GET);
echo '</pre>';
?>

And discovered that I would have the same results: xxx.yeloblog.com/some/test/url would work, but xananax.com/some/test/url would yield a 404 page. So this has nothing to do with wordpress.

For test purposes:

1. whatever.yeloblog.com/some/test/url
2. xananax.yeloblog.com/some/test/url
3. xananax.com/
4. xananax.com/some/test/url (should give same result as #2, but gives 404)

What should I do?

Here are the relevant configuration files: Apache conf:

<VirtualHost *:80>
    ServerAdmin root@localhost
    ServerName yeloblog.com
    ServerAlias *.yeloblog.com
    ServerAlias *.rassapark.com
    ServerAlias *.yelostudio.com
    ServerAlias *.xananax.com
    ServerAlias *.sabinecuisine.com


    DirectoryIndex index.html index.htm index.php
    DocumentRoot /my_root/

    RewriteCond %{HTTP_HOST} ^www.yeloblog.com$ [NC]
    RewriteRule ^(.*)$ http://yeloblog.com/ [R=permanent,L]

    <Directory /my_root>
            Options Indexes FollowSymLinks MultiViews
            AllowOverride All
            Order allow,deny
            Allow from all
    </Directory>

and .htaccess:

Options +FollowSymlinks +Indexes

#Wordpress Multi site
    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]

#END WordPress Multi Site

I tried mapping the domains in two different ways:

1. through the domain mapper plugin
2. by following the instructions in this post

In both cases, the process is the same:

• wildcard matching on serveralias
• wordpress takes care of redirection

In both cases, the result is the same: the domains are correctly mapped, and calling the posts through GET (ex: xananax.com/?p=123) works, but rewritten urls (xananax.com/2011/mm/dd/post_name) stop working (although they do work on non-mapped domains, e.g. accessing the same post through xananax.yeloblog.com/2011/mm/dd/post_name).