iptables not properly denying [FIXED]

Set the default rules, as desired:

iptables -P INPUT DROP
iptables -P FORWARD DROP
iptables -P OUTPUT DROP

I think you your case, you just want to default the INPUT policy to DROP. With your current rules, if you DROP all 3 noted above, you will find yourself without any usable services.

Thanks for the suggestion, I tried that, giving:

rules:

filter
:INPUT ACCEPT [368:102354]
:FORWARD ACCEPT [0:0]
:OUTPUT ACCEPT [92952:20764374]
-P INPUT REJECT
-A INPUT -i lo -j ACCEPT
-A INPUT -m conntrack --ctstate RELATED,ESTABLISHED -j ACCEPT
-A INPUT -i eth0 -p tcp -m tcp --dport 22 -j ACCEPT
-A INPUT -i eth0 -p tcp -m tcp --dport 80 -j ACCEPT
-A INPUT -m limit --limit 5/min -j LOG --log-prefix "iptables denied: " --log-level 7
-A INPUT -j REJECT
COMMIT

ben@sigma:~$ sudo iptables -L
Chain INPUT (policy DROP)
target     prot opt source               destination         
ACCEPT     all  --  anywhere             anywhere            
ACCEPT     all  --  anywhere             anywhere            ctstate RELATED,ESTABLISHED 
ACCEPT     tcp  --  anywhere             anywhere            tcp dpt:ssh 
ACCEPT     tcp  --  anywhere             anywhere            tcp dpt:www 
LOG        all  --  anywhere             anywhere            limit: avg 5/min burst 5 LOG level debug prefix `iptables denied: ' 
REJECT     all  --  anywhere             anywhere            reject-with icmp-port-unreachable 

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)
target     prot opt source               destination  

However, running from my laptop, I still get all these open ports:

sudo nmap -r -v -O -PN 12.34.56.78

Starting Nmap 5.21 ( http://nmap.org ) at 2010-07-28 15:53 BST
Initiating Parallel DNS resolution of 1 host. at 15:53
Completed Parallel DNS resolution of 1 host. at 15:53, 0.01s elapsed
Initiating SYN Stealth Scan at 15:53
Scanning li123456.members.linode.com (12.34.56.78) [1000 ports]
Discovered open port 22/tcp on 12.34.56.78
Discovered open port 80/tcp on 12.34.56.78
Discovered open port 2160/tcp on 12.34.56.78
Discovered open port 2161/tcp on 12.34.56.78
Discovered open port 2170/tcp on 12.34.56.78
Discovered open port 2179/tcp on 12.34.56.78
Discovered open port 2190/tcp on 12.34.56.78
Discovered open port 2191/tcp on 12.34.56.78

... Carries on up to port 10000

FIXED:

The version of nmap I am using has a bug! I just tried with google and got the same result. How embarrassing!

It's not nmap's fault, it's your ISP doing some transparent filtering/proxying/redirection.