I changed the host for some of my sites and the first thing, 4 days after the moving, they lost their serps. Instead of the first page, they started to appear in the 4th and 5th pages. Is this regular? Did you hear about it before?
If your host is on another service, in a different country then it could effect your regional SERPs, I guess.