I know it's exceedingly obvious , but is the website hosted on the same server that's the "down" nameserver? Have you confirmed that the records at the working nameserver are actually correct (i.e. pointing to the right IP, et cetera)?
Failing that, you might want to try traceroutes to both nameservers and the webserver; it could be a network problem somewhere.
redpin.com - offering amazingly competent email, dns, and web hosting since 2002... because someone has to!
Because Simple Things Should Be Simple - YouCANHasDNS