A few pointers - an outage or server move will not have any SEO impact for an established site.
Check your new IP's reputation - senderbase.org is a good starting point. Also check the IP's for any blacklistings multirbl (http://multirbl.valli.org/lookup/) is a good choice here. Especially with shared hosting or bad ASN reputation you will not be able to recover.
Check Google Safe Browsing if your domain might have become blacklisted due to following in a listed ASN (or IP)
Check that your robots.txt is still correct - during a move this could have caused plenty of pain if all bots are disallowed
If you don't have site maps, ensure that they are in robots.txt and are automatically submitted to Google
GWMT is your first port of call - check crawl speed, page speed and perhaps scan your site with webpagetest.org. While not obvious, a misconfigured HTTP (i.e. ETAGS on, no caching policies or even overwriting HTTP headers could cause this
Ensure that your Google Analytics (GA) account is still properly linked and records traffic
The above should pretty much narrow your problem down quite quickly. I do think it is either a HTTP issue (headers), robots.txt (if crawl-rate dropped) but more likely IP-address issues, provided that your site structure has not changed.
As a quick fix:
Regenerate sitemaps and resubmit
Pedantically go through GWMT and resolve any soft-404's or 404's by using 410's (SC_GONE) or 301 redirects.
You should have really done the following:
- Set your DNS TTL to 60 minutes
- Have your site provisioned on the new server infrastructure
- Switch A-/C-NAME records to point to new server infrastructure
- Change DNS TTL later on to a more reasonable time
During the DNS propagation (sometimes up to 3 days) some traffic will hit your new server and some traffic your old. This would have avoided any crawl issues altogether. But like I said, downtime would not affect SEO at all - unless your site was down for more than a week and even then you are able to "kickstart" it quite quickly.