1. Double-check that you set dedicated to 2 (internet), not 1 (default)
2. Allow ALL traffic to 30720 (or whatever is your server port) and outgoing acces to port 30710 (master server, hopefully i remember the port correctly). Some of firewalls (zone-alarm, for example) take out traffic to udp port 30720, called "Normal internet background noise".
3. Make sure that the server ip is not listen on master server ping timeout list (check list of servers:
http://tremmap.quakedev.org), if it is listed as ping timeout, your firewall (ISP or router may block it too) prevents access to tremulous server.
Ok, too much shit, tell you results and i will tell more

(Which OS u are using?)