Adding new sites to Pro Sites is not working well

I've set up multisite and install Pro Sites. I have set up my Wildcard DNS with my host company. Yet, when I add a new site, such as test.domain.com it's yielding a 404 error. When I'm go to Sites > All Sites and then click on the Dashboard link it shows the 404 error page. When I click the Edit link, I see the Info, Users, Themes and Settings tabs. I can make edits in here, but I still can't get it to load the new theme I added. I just see the 404 error page. Any help would be appreciated. Thanks!