Google does have hiccups once in a while...okay...pretty damn frequently. I've had a site de-indexed for no reason and then re-indexed many weeks later.
As an alternative, have you checked to see if the new host has Google issues or done an ip neighbors check?
If everything is checking out fine, then Google has probably had one of their infamous hiccups (remember when the entire web was harmful to your computer?) and it will probably be sorted out within a few weeks; they are in no hurry as it does not affect them.