If the move was pretty smooth - and the new host is sound, then you should recover equally quickly; you may have missed a round of spidering. Few experience even a dip.
If the problem is prolonged, while I cannot say 'it's NOT the host change', history says that really is MOST unlikely.
I'd seriously suggest either a faulty setup with the new host/server - or an unfortunate coincidence.
If the move involved serious site rebuilding or navigation changes, that's a different story.
Either way, start from the premise "This Should Not Be Happening" - and look very carefully at any other possibility.
[added:] First thing to check for is that the new host has any necessary 301s in place, such as non-www to www. Check also any long forgotten redirects that may have been useful. Do check your navigation - xenu is your friend.
[edited by: Quadrille at 3:58 pm (utc) on Sep. 20, 2006]