I had this problem, I think i solved it by entering this into my system.cfg file (not my brothers, left his running on port 64000)
net_lobby_gamespy_online_port = 64101 [DUMPTODISK]
Not dead sure this solved it, as i did about 3 separate fixes at once, so one of them worked. No im not going to fiddle with it to isolate it, it works, and thats all i care about.
Other things i attempted, that i can remember doing anyway.
1- port forwarding on the router (made it worse IRC, disabled atm and it still works)
2- MAC binding IP addresses to each computer. (didn't enable strict bind, but i forced the router to assign specific IP's to each of us.)
3- other stuff, i dunno, it was ages ago

And yeah, make sure you've got separate cd keys (if crytek ever turned cd key detection back on)