tedster - 4:39 am on May 28, 2013 (gmt 0)
Hello, and welcome to the forums!
Actually we changed our hosting server on 8th May, got a new IP, changed A Record and used same DNS.
That's the first thing I would check into. There are several DNS checking sites online that should help you do this. There are over 50 ways a DNS can be setup up incorrectly, and I've only ever checked one domain that had no Errors or Warnings.