I have followed the network Configuration instructions for mutlisite installation very carefully.
It's a new wordpress 3.6 installation.
I have set up a wildcard (*) at my host dns.
My host says that everything looks good with the wildcard and they have many multisite with subdomains costumers and says i should contact wordpress support.
PROBLEM: When I add a new site in the network and try to visit the new subdomain site i get a 404 error.