PLEASE do NOT suggest "uninstall/reinstall" as the FIRST course of action in any problem....
It should only be used after "less severe" measures are taken first, since "Un-/Re-install" CAN cause problems itself. (Most often missing in-game text....)
Anyway...
The Halo GameSpy lobby is on death's door, and is no longer a very reliable way to look up games. Keep that in mind while you try the things listed above to DISABLE any possible server filtering that might have gotten enabled.
After that, try comparing your Lobby results with someone else (in chat, or voice) and see if it really IS different.... (I.e Don't trust what you EXPECT to see in the Lobby!)