On a practical level. Did traffic from Direct and referring sites also drop by the same percentage, if so then Google is not the issue.
Check the server error logs, and the MYSQL error logs for clues as to a technical issue. A simple mis configuration can cause an issue. Run a full set of DNS tests and make sure the server is resolving properly.
Are both servers identical in their setup? Do they provide the same headers, etags etc.... Is the firewall configured correctly?
Run as many traceroutes as you can from different locations and machines and see if the new provider is having network issues.