Forum Moderators: phranque
I've moved sites from one hosting company to another with no effect at all on search results.
One site I worked on is hosted by a company that is as bad as the one you mention. Or worse. Unfortunately, the guy who runs the hosting outfit is a cousin of the president of the company I did the site for, so you get the idea.
I feel your pain, brother - I am still mopping up after moving 100+ domains.
If you want any advice on switching the nameserver, post. If you would like some tips on the new host, PM me. I can vouch for a few I've used personally.
Have a nice day!