Just a few things to limit this problem. Some may not be related, but the least amount of potential issues the better:
I dont not have firestarter nor any other firewall software running.
Your system is still running iptables most likely. Firestarter is just a GUI to allow easier control over firewalls. I ran Counter Strike with Firestarter and didn't have any blocked accesses or any issues. So I do not think that the firewall would be the issue.
Also, are there servers visible, or are you crashing every time you connect?
Lastly, and this might sound weird, but I would change your audio driver to OSS. I have had weird issues using other drivers. The whole game play experience seems better with OSS...