If they do a ping or host lookup on their computer for your domain, do they come up with the proper IP address for it? That's the first place to start, is to make sure they are getting the right IP. If they are running windows, just have them ping your domain name in a cmd window and see what they get back.