Yo tambien me compre este juego a traves de Steam y me dio, entre tantos, ese problema. Pero finalmente consegui resolverlo, a lo mejor simplemente será que tienes que esperar y cuando te conectes al siguiente dia ya te funciona. Aun asi haz lo siguiente:
1º- No hace falta que quites el firewall de windows, simplemente abre los puertos que utiliza el COD4 (UDP 20800, UDP 20810, UDP 28960).
2º- Echale un ojo a lo siguiente: https://activision.custhelp.com/cgi-bin/activision.cfg/php/enduser/std_adp.php?p_faqid=19511&p_created=1194554858&p_sid=1zdvlagk&p_accessibility=0&p_redirect=&p_srch=1&p_lva=&p_sp=cF9zcmNoPTEmcF9zb3J0X2J5PSZwX2dyaWRzb3J0PSZwX3Jvd19jbnQ9MTAxMjUsMTAxMjUmcF9wcm9kcz0wJnBfY2F0cz0mcF9wdj0mcF9jdj0mcF9zZWFyY2hfdHlwZT1hbnN3ZXJzLnNlYXJjaF9ubCZwX3BhZ2U9Mw!!&p_li=&p_topview=1
3º- Ve a la web oficial de punkbuster y descargate el archivo para luego instalarlo y actualizarlo manualmente: http://www.evenbalance.com/index.php?page=support-cod4.php
4º- No uses Steam para jugar al COD4. Descargate el Xfire y unete a los servers desde ahi. El Steam da muchos fallos para este juego, no se por que la verdad. De todas formas, desde el juego no se encuentran apenas servidores, su buscador da pena, asi que yo que tu usaria el Xfire.
PD: Si utilizas win7 y no deja unirte a algun servidor (me pasaba a mi) se puede resolver facilmente: busca iw3mp.exe y xfire.exe click derecho>propiedades>compatibilidad y le das a cambiar la configuracion para todos los usuarios luego marcas la casilla de ejecutar como administrador y en modo de compatibilidad pon windows xp (no importa que service pack).
¡Un saludo!