One guy got back to me with his ping results:
"ping request could not find mydomain.com"
I've already had this guy try flushing his dns a while ago, no luck.
It's been over a month since I changed hosts, so I thought this would clear up by now.
Was about to suggest having them both DNS your site to ensure that the host change has propagated to their system;
Gizmo, can you explain a little more what you mean, thanks.