I can ping the Exchange server here at work, but Outlook doesn't connect to it. I've verified the server is indeed the Exchange server and I've tried using the IP instead of the server name. I am also able to connect to port 135 using telnet (although nothing useful happens). I also tried running a trace using Wireshark but the protocols Outlook uses are proprietary and I couldn't see anything useful in the trace.
I'd love to hear some other steps I could take to track down the problem.