Well, if you took the firewall down and you still can't connect, that suggests that vncserver isn't doing its job. If you run ps -A you should see that Xvnc is running and if you do a netstat -l or [/B]nmap localhost[/B] you should see that something is listening on the appropriate ports.
As for restarting your firewall, it may depend on how you normally start it. On my machine I just have to run a script (/etc/rc.d/rc.firewall) and its up. I"m not sure about RedHat, though maybe service iptables restart will do the trick.