Depends on your distro and on your firewall... In general it's a good idea to have a look at the init scripts in /etc/init.d. Maybe there's one with the string "firewall" in it? If so, run
to see if it has really stopped. If this doesn't help or you can't find an init script for your firewall run
That flushes all you firewall rules.