Try doing the DNSReport, DNS Timings and ISP Cached DNS Lookup at http://www.dnsstuff.com/
Did your DNS host also change?

I've seen ISP's that cache DNS for almost two weeks an other ISP's that have very bad DNS servers this is why I recommend using Treewalk DNS.