I've got a new premium dedicated server with Bytemark. Remote console, ipv6, good support.

The machine came with Maverick (Ubuntu 10.10) installed, so I upgraded to Natty (11.04). Note: you need to first install iptables, or do-release-upgrade fails (filed as Ubuntu Update Manager Bug #794590).