I had the same error, at first it was domain.tld.com
I'm the only one creating the subdomains as its a rather new site and it worked fine for about a few days till 2 to 3 days ago.
domain.tldBASEsiteupdate/ (username is siteupdate)
domain.tldBASEupdate/
domain.tldBASEtest1/
domain.tldBASEfasddf/ (I started just typing in stuff like fasddf for username)
Then after replacing .htaccess with the default htaccess file (and using the line 'RewriteBase /' instead of the default line ) it became.
angloindianblogs.comBASEss2007/
angloindianblogs.comBASEpackage50tol/ (username package 50tol)
angloindianblogs.comBASElpackagetompackage/ (username package lpackagetompackage)
It started about 2-3 days ago, and I've installed about 10 modules and not sure which modules required me to manually change key files. I remember adding 2 captcha plug ins wpmu-signup-captcha and WP Captcha 1.0 for wordpress mu 1.2.4 - 1.2.5a
pgesystems can you recall which modules you added after the new subdomain registration errors started?