I believe these ports need to be opened to host.
13139 (Custom UDP Pings)
6500 (Query Port)
2302 (DirectPlay - UDP)
if that does not fix the problem...Open up civ go into multiplayer, and host a game. Then bring up task manager. in task manager(assuming you are using xp) go into view and then select columns. there should be a box labelled PID(Process Identifier) check that box. then close that and open the processes tab. Scroll and find civilization3x or whatever it is called and look what the 4 number PID is. write it down. make sure civ is still open and you are still hosting a game. Go into command prompt and type "netstat -o -a". there will be 5 thing you see: Proto, Local address, Foreign address, State, and PID. under PID search for the civ PID. there will probably be more than one. when you find one, look under its local address and there will be the name of your computer and a port number. that is a port that is trying to get through, make sure you have it open. MAke sure all of the ports the have the civ PID code are open.
I hope this was readable. If this doesn't work or you still need more help just pm me.
