I will agree that it is a DNS problem. Using my DSL connection I get inconsistent results looking up your domain name. Sometimes I get a response, other times I get a 2s timeout, other times I get a complete timeout.
I just checked your domain (rotojunkie.com)...it's in all of the gTLD servers with consistent results...so that's not the problem...both of the name servers for your domain name (ns5.nocservers.net and ns6.nocservers.net) are in all of the gTLD servers with consistent results...so that's not the problem...the domain name of the name servers (nocservers.net) is listed in all of the gTLD servers with consistent results, and both of the name servers for nocservers.net (ns.nocservers.net and ns2.nocservers.net) are in all of the gTLD servers with consistent results...so that rules out all of the registry problems...
I just checked your host's name servers, and they've got a really big mess. The NS records for nocservers.net aren't consistent with the ones in the gTLD servers, nor are the NS records consistent between all of their name servers. They also don't have ns5.nocservers.net and ns6.nocservers.net in their name servers, which is what I believe is causing the problem in your case.
Contact your host again as this is definitely a problem on their end, and if they continue to deny something is wrong, then they're incompetent and you need to find a new host.
What you really need to do to nail down the issue if its DNS or not is when your customers call complaining about not getting to a site, ask them for the DNS server they are using, then do a nslookup using their DNS server, and that should give you a clear picture of whats going on, also make sure to use the "set d2" option so you can see what nameservers it forwards the query to.
Jay Kramer - Operations Manager
Affordable Colocation and Dedicated Servers www.colostore.com 1-877-719-3698