DNS propagation can take up to 72 hours. Usually it's 24 or less unless you're like in a 3rd world country with a tin can and a string for internet.
You change the name servers for your domain, set up the required DNS entries (including the wildcard entry), and then wait.
Each "subdomain" won't have to propagate, they're wildcards with your DNS.
The "big picture" is that your new name servers have to propagate first. What you "could" try to fix is the IP in your old DNS settings, and point it to the new IP address. Which may/may not help.
Regardless of what's going on, if you switch hosts on a whim you'll have this problem no matter where you go.
The work around for the DNS propagation time is pretty simple, but you have to plan out your change prior to.
An example of this would be...
1-2 weeks out:
Set the ttl very, very low on your "current" DNS. I mean like a ttl of 180 - 300 seconds (3-5 minutes). Setting this early ensures that the ttl is propagated. This will increase lookups for your domain, but that's what you want.
96 hours prior to the move:
Warn your users that you will be performing server maintenance in 4 days, and that in order to prep for it you will be locking out new registrations, and any administrative access to their accounts 24 hours prior to the maintenance window.
24 hours prior:
Lock out users from wp-admin, redirect all logins to your main page instead of wp-admin. Use a temporary modified wp-login for this, and back up the original so you can restore it.
Take a dump of the database, once users are locked out.
If it's "really big", break up the dump into multiple files so when you import it doesn't puke.
Verify the dump, twice if not three times.
Tar up your entire public directory, and make it an "obscure" name. Stick it in your public accessible directory.
Log into your new account location.
At this point, you've hopefully had the modifications to the vhost made for apache, as well as set up your new DNS values (like the wildcard).
Move your tar file over to the new server. Put it on the same level as your root html directory (public_html, or whatever) so that when you are at the level above the public html root, you see your new one, and the extracted one at the same time.
Use mv, and move the old one over the new one, keeping the name of the new one. (mv old_one new_one, for example)
Now you have a mirrored the file structure from the old account.
Now, create the new db(s). Hopefully the db names are the same.
Import the dump, and then modify wp-config.php if required (so it can connect to the db).
Make an edit to your local computers hosts file, so that domain.com points to the new IP address. Also add a couple subdomains to your host file, and point them to the same IP. (Note, not editing the server's hosts file, the one on your computer)
Make a quick edit to the theme you're using for your primary site. Something simple, and unnoticeable to someone not looking for it. (like an html comment in the header).
Check the new site, view the source in your browser and check for your "change".
Try logging in.
Verify you can get into the dashboard, etc. Test permalinks, and all that jazz.
Once it's working, it's time to boogie.
Remove your edits to your local machines hosts file. Verify you are correctly taken to the old site. (You'll know, as there won't be your little "modification" to the theme).
Change the name server values to the new ones, wherever you have your domain registered.
Wait a few minutes, then try your domain. It should be headed to the new location now, provided you updated your TTL in the first step properly, and verified it took.
The CYA:
I claim no warranty to the above example, and if you try it it's at your own risk. I also offer no support for it. It is an advanced issue, and should be treated as such. In short, it's not for the weak of heart, or those with a lack of knowledge required for sever administration and hosting.
Sorry for the wind, but the example might be useful to someone. I've done it myself many times when moving accounts from server to server, or shared server to dedicated, or whatever. Anyone referencing it will have to adapt it to their situation, etc.