This is exactly what is happening to me.
I have Halo 3, and COD4 beta currently. I play Halo 3, my connection is at 1 red bar in game. I leave, I enter COD4 beta and I get a 3-4 green bar connection, no lag at all, plays fine.
My NAT is set to open, I can join matchmaking games, I can participate in them, but the lag is so bad that I cant do anything in game.