Firewall as a first impression... I had some problems like yours when trying to play with a person whose pc was firewalled.
Also, if you are trying to play with LAN, do not flag the "Internet play" check-box. Do so instead if playing on Internet via TCP/IP.
Finally, both of you must try to be the host, but not contemporarily of course. Probably one PC (or both of them?!) have a firewall configuration that prevent detecting the other host... So let you try to find who is the PC that can't host... and what to do in the firewall setup in order to fix the problem.
I had similar problems when testing the MP over the LAN. My desktop was not able to host the game... never! Damned windows! So I always used the laptop as server and the desktop as client.