I am trying to open port 3306 (for remote mysql connections) on my ubuntu 12.04 server machine but for the life of me can't get the damned thing to work!

Here is what I did:

1) list current firewall rules:

$> sudo iptables -nL -v

output:

Chain INPUT (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
  225 16984 fail2ban-ssh  tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            multiport dports 22
  220 69605 ACCEPT     all  --  lo     *       0.0.0.0/0            0.0.0.0/0
    0     0 REJECT     all  --  lo     *       0.0.0.0/0            127.0.0.0/8          reject-with icmp-port-unreachable
  486 54824 ACCEPT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            state RELATED,ESTABLISHED
    1    60 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:80
   19   988 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:443
    1    52 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            state NEW tcp dpt:22
    0     0 ACCEPT     icmp --  *      *       0.0.0.0/0            0.0.0.0/0            icmptype 8
    4   208 LOG        all  --  *      *       0.0.0.0/0            0.0.0.0/0            limit: avg 5/min burst 5 LOG flags 0 level 7 prefix "iptables denied: "
    4   208 REJECT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable

Chain FORWARD (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
    0     0 REJECT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable

Chain OUTPUT (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
  735  182K ACCEPT     all  --  *      *       0.0.0.0/0            0.0.0.0/0

Chain fail2ban-ssh (1 references)
 pkts bytes target     prot opt in     out     source               destination
  225 16984 RETURN     all  --  *      *       0.0.0.0/0            0.0.0.0/0

2) try to connect from remote machine:

$> mysql -u root -p -h x.x.x.x

output:
timeout.... failed to connect

3) try to add a new rule to iptables:

iptables -A INPUT -i eth0 -p tcp -m tcp --dport 3306 -j ACCEPT

4) make sure the new rule is added:

$> sudo iptables -nL -v

output:

Chain INPUT (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
  359 25972 fail2ban-ssh  tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            multiport dports 22
  251 78665 ACCEPT     all  --  lo     *       0.0.0.0/0            0.0.0.0/0
    0     0 REJECT     all  --  lo     *       0.0.0.0/0            127.0.0.0/8          reject-with icmp-port-unreachable
  628 64420 ACCEPT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            state RELATED,ESTABLISHED
    1    60 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:80
   19   988 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            tcp dpt:443
    1    52 ACCEPT     tcp  --  *      *       0.0.0.0/0            0.0.0.0/0            state NEW tcp dpt:22
    0     0 ACCEPT     icmp --  *      *       0.0.0.0/0            0.0.0.0/0            icmptype 8
    5   260 LOG        all  --  *      *       0.0.0.0/0            0.0.0.0/0            limit: avg 5/min burst 5 LOG flags 0 level 7 prefix "iptables denied: "
    5   260 REJECT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable
    0     0 ACCEPT     tcp  --  eth0   *       0.0.0.0/0            0.0.0.0/0            tcp dpt:3306

Chain FORWARD (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
    0     0 REJECT     all  --  *      *       0.0.0.0/0            0.0.0.0/0            reject-with icmp-port-unreachable

Chain OUTPUT (policy ACCEPT 0 packets, 0 bytes)
 pkts bytes target     prot opt in     out     source               destination
  919  213K ACCEPT     all  --  *      *       0.0.0.0/0            0.0.0.0/0

Chain fail2ban-ssh (1 references)
 pkts bytes target     prot opt in     out     source               destination
  359 25972 RETURN     all  --  *      *       0.0.0.0/0            0.0.0.0/0

which appears to be the case (last line in "Chain INPUT" section).

5) try to connect again from remote machine:

$> mysql -u root -p -h x.x.x.x

output:
timeout.... failed to connect

which is failing again.

6) try to flush all rules:

$> sudo iptables -F

7) this time I CAN CONNECT.

8) reboot server and try to connect, FAILURE.

I suspect since the new rule is being appended at the end it will have no effect as there appears to be a "reject all" sort of rule before it. If this is the case, how to make sure the new rule is added in the right order? Otherwise, what am I missing?

Please help.