Multisite: Subsites are not displaying

I have installed multisite at bluehost. I followed the instructions to edit .htaccess, etc. and I added a wildcard A record to point my main domain ( The problem comes when I add a new site ( WPMU acts as if it was a success however, I get a “404: File Not Found” when I try to access it. It seems that WPMU isn’t able to create the subdomain. Any suggestions? I’m struggling!