Well you could try downloading
qstat and run a query against the query port (6500) to see if it even replies locally. If it doesn't you have an issue somewhere with the game setup. If it does then you may have a gamespy login issue.
qstat -R -gs4 x.x.x.x:6500
On my NAT'd server I can run the query on the LAN ip internally and it responds ok, then from outside the network i can do the same for the Internet address.
That's all i've got for suggestions, good luck.