It could be any number of things. In the beginning, my civ buddy and I always had
problems too, but eventually we got them ironed out. So, keep working at it.
Maybe you could provide some more information. Are either of you getting any error?
Have you both followed all of the settings about routers/firewalls in the information sections? Are you playing a mod, homemade map/scenario or regular game? Have you ever gotten one successful start?
Anyway, after the staging room screen, sometimes it takes a while to hook up to the other person before we both meet on the game settings screen. (At least for me.)
Lastly, without knowing anymore, I would say that make sure you both, or even a computer civ, aren't trying to get in the same player slot e.g. both be player one. That caught us once or twice.