Yeah, it is all patched up, and everything is in working order.
The problem is that Company Of Heroes is a P2P game when it comes down to the networking level, so every player has to connect to every other player.
So when only one of us is playing the game over the internet it is fine, and neither of us get "xxxx Player failed to connect"
But if both of us are playing in different COH online matches, or the same match some online players can't connect to my machine or my friends machine, or both.
I'm starting to think that it might just be a issue with COH not knowing what to do when one public IP address has two sessions running. Games like CS:S and TF2 work just fine mainly because I think that Valve put a bit more thought into online play (I.E. people have more than one gamer in the house) than Relic/THQ has.
I'm going to try forwarding the ports to both machines, but I am really starting to think that it is a issue with the program and not my network.