Our DNS server seems to be responding just fine. In fact, the people we have switched over to the other gateway are still using the same DNS server (An old Windows 2000 machine) as the rest of us, except for the fact that they are working just fine.
What has me really confused about this issue is that the same thing is happening to me at home, and I am using a completely different DNS server that the one I use at the office.