In fact, even using "service iptables stop" might cause the entire box to hang
due to the
above described problem! This is rare but it happend twice to me. Please
interchange the
order of changing the policies and flushing the chains in the init script!

#!/bin/sh
#
# Startup script to implement /etc/sysconfig/iptables pre-defined rules.
#
# chkconfig: 2345 08 92
#
# description: Automates a packet filtering firewall with iptables.
#
# by bero, based on the ipchains script:
# Script Author:	Joshua Jensen <joshua>
#   -- hacked up by gafton with help from notting
# modified by Anton Altaparmakov <aia21.uk>:
# modified by Nils Philippsen <nils>
#
# config: /etc/sysconfig/iptables

# Source 'em up
. /etc/init.d/functions

IPTABLES_CONFIG=/etc/sysconfig/iptables

if [ ! -x /sbin/iptables ]; then
	exit 0
fi

KERNELMAJ=`uname -r | sed                   -e 's,\..*,,'`
KERNELMIN=`uname -r | sed -e 's,[^\.]*\.,,' -e 's,\..*,,'`

if [ "$KERNELMAJ" -lt 2 ] ; then
	exit 0
fi
if [ "$KERNELMAJ" -eq 2 -a "$KERNELMIN" -lt 3 ] ; then
	exit 0
fi



if  /sbin/lsmod 2>/dev/null |grep -q ipchains ; then
	# Don't do both
	exit 0
fi

start() {
	# don't do squat if we don't have the config file
	if [ -f $IPTABLES_CONFIG ]; then
            echo -n $"Resetting built-in chains to the default ACCEPT policy:"
   	    iptables -P INPUT ACCEPT && \
	      iptables -P OUTPUT ACCEPT && \
	      iptables -P FORWARD ACCEPT && \
	      iptables -t nat -P PREROUTING ACCEPT && \
	      iptables -t nat -P POSTROUTING ACCEPT && \
	      iptables -t nat -P OUTPUT ACCEPT && \
              iptables -t mangle -P PREROUTING ACCEPT && \
              iptables -t mangle -P OUTPUT ACCEPT && \
	      success $"Resetting built-in chains to the default ACCEPT 
policy" || \
	      failure $"Resetting built-in chains to the default ACCEPT policy"
            echo
	    # If we don't clear these first, we might be adding to
	    #  pre-existing rules.
	    action $"Flushing all current rules and user defined chains:" 
iptables -F
	    action $"Clearing all current rules and user defined chains:" 
iptables -X
	    chains=`cat /proc/net/ip_tables_names 2>/dev/null`
            for i in $chains; do iptables -t $i -F; done && \
              success $"Flushing all current rules and user defined chains:" 
|| \
              failure $"Flushing all current rules and user defined 
chains:"	    
            for i in $chains; do iptables -t $i -X; done && \
              success $"Clearing all current rules and user defined chains:" 
|| \
              failure $"Clearing all current rules and user defined chains:"

            for i in $chains; do iptables -t $i -Z; done

	    echo $"Applying iptables firewall rules: "
		grep -v "^[[:space:]]*#" $IPTABLES_CONFIG | grep -v 
'^[[:space:]]*$' | /sbin/iptables-restore -c && \
		    success $"Applying iptables firewall rules" || \
		    failure $"Applying iptables firewall rules"
	    echo
	    touch /var/lock/subsys/iptables
	fi
}

stop() {
	chains=`cat /proc/net/ip_tables_names 2>/dev/null`
        echo -n $"Resetting built-in chains to the default ACCEPT policy:"
	iptables -P INPUT ACCEPT && \
	   iptables -P OUTPUT ACCEPT && \
	   iptables -P FORWARD ACCEPT && \
	   iptables -t nat -P PREROUTING ACCEPT && \
	   iptables -t nat -P POSTROUTING ACCEPT && \
	   iptables -t nat -P OUTPUT ACCEPT && \
           iptables -t mangle -P PREROUTING ACCEPT && \
           iptables -t mangle -P OUTPUT ACCEPT && \
	   success $"Resetting built-in chains to the default ACCEPT policy" 
|| \
	   failure $"Resetting built-in chains to the default ACCEPT policy"
	echo
        for i in $chains; do iptables -t $i -F; done && \
                success $"Flushing all chains:" || \
                failure $"Flushing all chains:"
        for i in $chains; do iptables -t $i -X; done && \
                success $"Removing user defined chains:" || \
                failure $"Removing user defined chains:"
	echo
	rm -f /var/lock/subsys/iptables
}

case "$1" in
  start)
	start
	;;

  stop)
	stop
	;;

  restart)
	# "restart" is really just "start" as this isn't a daemon,
	#  and "start" clears any pre-defined rules anyway.
	#  This is really only here to make those who expect it happy
	start
	;;

  condrestart)
	[ -e /var/lock/subsys/iptables ] && start
	;;

  status)
	echo $"Table: filter"
	iptables --list
	echo $"Table: nat"
	iptables -t nat --list
	echo $"Table: mangle"
	iptables -t mangle --list
	;;

  panic)
	echo -n $"Changing target policies to DROP: "	
	iptables -P INPUT DROP && \
	    iptables -P FORWARD DROP && \
	    iptables -P OUTPUT DROP && \
	    iptables -t nat -P PREROUTING DROP && \
	    iptables -t nat -P POSTROUTING DROP && \
	    iptables -t nat -P OUTPUT DROP && \
	    iptables -t mangle -P PREROUTING DROP && \
	    iptables -t mangle -P OUTPUT DROP && \
	    success $"Changing target policies to DROP" || \
	    failure $"Changing target policies to DROP"
	echo
        iptables -F INPUT && \
                iptables -F FORWARD && \
                iptables -F OUTPUT && \
                iptables -t nat -F PREROUTING && \
                iptables -t nat -F POSTROUTING && \
                iptables -t nat -F OUTPUT && \
                iptables -t mangle -F PREROUTING && \
                iptables -t mangle -F OUTPUT && \
                success $"Flushing all chains:" || \
                failure $"Flushing all chains:"
        iptables -X INPUT && \
                iptables -X FORWARD && \
                iptables -X OUTPUT && \
                iptables -t nat -X PREROUTING && \
                iptables -t nat -X POSTROUTING && \
                iptables -t nat -X OUTPUT && \
                iptables -t mangle -X PREROUTING && \
                iptables -t mangle -X OUTPUT && \
                success $"Removing user defined chains:" || \
                failure $"Removing user defined chains:"
        ;;

  save)
	echo -n $"Saving current rules to $IPTABLES_CONFIG: "
	touch $IPTABLES_CONFIG
	chmod 600 $IPTABLES_CONFIG
	/sbin/iptables-save -c > $IPTABLES_CONFIG  2>/dev/null && \
	  success $"Saving current rules to $IPTABLES_CONFIG" || \
	  failure $"Saving current rules to $IPTABLES_CONFIG"
	echo
	;;

  *)
	echo $"Usage: $0 {start|stop|restart|condrestart|status|panic|save}"
	exit 1
esac

exit 0

Oops, I might have said that this is what I had done to it. Anyway, look above 
and there you go.

I just again locked up a box by calling "service iptables stop". This is an
EXTREMELY ANNOYING BUG WHICH IS EXTREMELY EASY TO FIX, so please do it. Thanks.

Actually, I don't think it's such a good idea.
Imagine the following situation:

Someone has set up IP forwarding to his internal network for specific IPs only.
That user does "service iptables restart".
With your script, policies are changed to ACCEPT before the forwarding rules 
are deleted, and someone from outside can use that to crack a machine that 
shouldn't be accessible to him.

Neither order is the 100% right thing to do; I'd rather have a possible local 
problem on some machines only than allowing a remote exploit on any machine 
that does filtered forwarding.