No that had nothing to do with it, I have always used port ranges and never had an issue.
After messing with it and messing with I was able to recreate the problem when introducing the loopback NAT rule the public server wizard automatically adds in there so internal servers can reach the same resources as a WAN client would. For whatever reason that loopback fubar'd the communication to the Gamespy master servers and had it reporting the wrong port for the server.
Direct IP joins and joins from Xfire always worked, it was only through the Halo lobby the problem presented itself.
Oh well, it is resolved now and things are cooking again, thanks!
Bookmarks