I thought it was time to move to IPv6. And I did:

robi@akari:~$ ping6 -c 1 ipv6.google.com
PING ipv6.google.com(2001:4860:0:1001::68) 56 data bytes
64 bytes from 2001:4860:0:1001::68: icmp_seq=1 ttl=55 time=237 ms

--- ipv6.google.com ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 237.123/237.123/237.123/0.000 ms

I configured the router using this document: OpenWrt IPv6 howto.

No configuration were needed on the client side. We have linuces: Ubuntu 8.04 and Debian lenny, and they work out of the box.