A few questions. Does your site get a lot of "long tail" traffic? Is most of your organic traffic from Google?
If you answered yes to either, you may want to read the following thread:
Google made some big changes to their search algorithm in late April and it has taken its toll on a lot of website owner's organic traffic.
It could be coincidence, but perhaps your traffic loss has nothing to do with your host migration? I assume none of your file names or urls changed right?