do you have acces to your httpd.conf file?
when i first set mine up i could do everything but set up a new blog i would get the email activete ...etc and do all that but then couldn't actually go to the newly created blog...
I had to edit the httpd.conf file on my server to allow overide all instead of none
<directory "blogroot">
AllowOverride All
</directory>
I used subdirectories for my installation but they are still "virtual" subdirectories in that new blog is http://www.domain.com/test/index.php where the directory test/ doesn't actually exist on the server but is made by wpmu and is simply a value stored in the database, I know that it handles subdomains similairly.
If this doesnt help more info about what actually happens when you try to set up a new blog will help narrow down the problem.