Peter,
Just an FYI, with the DNS change your old provider was sending out SERVFAIL messages with long TTLs. This means many clients and DNS servers will cache this DNS negative response and folks will likely continue experiencing issues getting to you until the TTLs expire or they flush their caches. I had to flush my DNS server caches to get back to your domain.
Jeff
Bookmarks