Okay I get the same error about the game browsing server being unavailable.
I know my gamespyid is good as a friend was able to use it on his internet connection just fine.
From the network log
[98040.265] DBG: Resetting the portal! (m_bConnectComplete=false)
[98047.125] DBG: Resetting the portal! (m_bConnectComplete=false)
[98047.375] WRN: Disconnecting from entire Peer Network!
[98060.718] ERR: Unable to contact the matchmaking server
The in game message box is titled "Server unreachable"
with the text of the message being "The connection to the game browsing server has failed"
I do not have windows firewall enabled on any of my network interfaces. I did say yes during the installation to add the config info to the windows firewall though. I've tried connecting with the firewall enabled, disabled, with my machine plugged directly into the cable modem (removing the NAT from the equation. My firewall / router might have been the problem but plugging directly into the cable modem and getting an outside IP proves thats not the issue.)
I have windows XP SP2, an nForce 4 AMD motherboard without the nforce firewall installed. No other firewall or other filtering software is installed.
I used TCPView from Sysinternals and see that Civ causes "[System Process]:0 TCP MY.COMPTUERS.IP.ADDRESS:2561 207.38.11.34:29900 TIME_WAIT" messages to happen
The local port (2561 in this case) changes each time I attempt a connection in Civ but it doesnt seem to be working properly.
Whenever I call Take2 Support they disconnect the call after 5 minutes on hold saying I should email them. They are not responding to emails very fast.

Anyone have ideas?
I think this may have something to do with TimeWarner's Roadrunner IP block I am getting.
For the curious I have an airlink wireless router, the Airlink 101 Super G... its got the Firmware Version: 1.6.6 , 2005/03/30
But again I plugged directly into the cable modem ( I did MAC address spoofing on the router so my PC and the router report the same MAC to the DHCP servers. Makes swapping it out simple. )