Hello all!
I just wanted to share with you what I learned today from HostGator.
I have a VPS account and could not install WPMU on my root account, yet oddly… it would install fine on other domains which were hosted at Godaddy and pointed to my VPS as addons.
Turns out that adding the wildcard to the A Name records won't cut it. It will throw you to a Cpanel page that says the site doesn't exist after you create a new account on your WPMU.
Here's the fix
1. Remove the A Name record you created via DNS manager (e.g. *.yourdomain.com )
2. Now go to "Domains -> Subdomains" via your Cpanel and add your wildcard there. (e.g. *.yourdomain.com )
Once you've added your wildcard in the subdomains section (INSTEAD of the DNS area) – try to create a new site on your install – you may just find joy! I know I did after hours of frustration 
I manually installed to rule out other issues – but I wanted to share this info here because this plugin is really nice for people who don't know how to do it. It's also a great timesaver – so thank you for providing it 