New blogs (subdomains) 404 error

Hello.
I’m using WP 3.1.2 and I can’t seem to get multisite to work on my domain.
Check http://quadruplor.com/ – it’s my main domain where I’m trying to create a wp-multisite , I already created a blog http://haircuts.quadruplor.com/ through “Register” option, I recieved the activation-link email but when clicking on it, I get the 404 Error. The same thing happens if I try to “Visit” this newly created blog from Network Admin panel, just 404 error and no further information.

Any thoughts of what could be wrong? I double-checked the .htaccess and wp-config.php changes, that should be OK, I also created the wildcard DNS option as written in WordPress codex.