Multisite with subdomains

OKay, I have been at this for a week now and reading through the various suppoort posts and still cannot figure out how to make what I want to do work… The goal… I need to have a WP main site that I develop as the base main site. I then need to have subdomain sites for each unique community group of users that I can make each private to their respective sub sites. So for instance I have mydomain.com as the main site then users1.mydomain.com, users2.mydomain.com, etc. I wanted to use Multisite since all the sites will have the same plugin’s and theme to ease management. I have installed multisite, have the main site working fine and the network/site menu and such but I have been told the hosting company does not support wildcard subdomains even though they told me they did at first. They suggested I make a subdomain in the DNS zone file then use .htaccess to redirect to the main site. I have done this and created the subdomain site in WP but I still cannot get the subdomain site to work. What am I missing? I have WP 3.4 installed.

Thanks for any assistance.