Seem to be having a similar problem to this guy:
http://mu.wordpress.org/forums/topic.php?id=552
I got my host to do the wildcard and httpd file stuff and so my WPMU subdomains worked fine once that was done.
However, any existing subdomains I had created before WPMU installation now don't work (and resolve to the site home page). I have a support request in to my host, but they're taking ages to answer. Anyone else had this problem?
