My company just switched dns servers to zoneedit.com. We have two websites that run on the same server (same IP.) We only switched our DNS providers, we did not switch the IP of the server. 1 day after the switch, multiple servers around the world could ping and visit both servers and whois queries returned the new server host info. Now, no one in the world can see ONE of the domain names, but everyone can see the other one! Can anyone tell me why this might be, and maybe how we might go about rectifying the problem?

It looks like there might be a DNS issue. Either DNS propagation has not completed or the DNS hosts have not been set on the domain that's not working. Try to use dnsstuff.com to troubleshoot the problem.