Whenever I try to connect to my friend's server, the loading screen just says "Contacting Host" for a few minutes, then I get an error message stating "Cannot negotiate with host's firewall."

Both he and I have both disable our firewalls and tried opening ports up and stuff like that, but nothing seems to work.

Oddly enough, I can still connect to other people's servers.

Has anyone else had this problem or can anyone give me some advice?

I assume you both are behind routers. I had to open up port 2056 TCP and UDP ports. Remember, you also have to forward those ports to a private ip address. For instance, your router's ip address is public, that's the IP addy that people will put in the join games. In your router settings (especially if you have more then one computer hooked up to it) you have to tell the router what private ip addy (local computer) to forward those port requests to. Usually each private computer addy with start with a 192.168.*.* Unfortunately each router setup page is different and it's hard to tell someone exactly how to do this.