I would do the obvious and scan for viruses.

Once that has been ruled out consider the other possibility. Someone has installed a DNS program. (We found a good one on the net that changed a client into a full blown DNS server).

Also double check your DNS server and the clients. Its possible they may somehow be pointing to another machine outside the firewall (very unlikely).

I'm really not sure what else you could check except maybe the firewall/router to make sure no one has gained access to it.

Good Luck.