my mate has had problems also with COD4 and he has a router also. So don't think your alone.
he said to to me that he tested the internet connection with the router and the only difference he seen was the NAT types. With the router, it was NAT3, without it, it was NAT1. (No idea what an NAT is lol )
After he disconnected the router and hardwired to his cable modem, he was able to connect to the online side.
hope you have got it sorted