To join the fun of World IPv6 Day, I decided to setup IPv6 connectivity to the Digital Engine office. This was accomplished using Hurricane Electric's awesome (free) tunnelbroker.net service. All went smoothly, except that the office gateway, running Debian Squeeze (Linux), would not forward IPv6 traffic from computers on the network. Traffic originating at the gateway worked fine, traffic originating on the local network was silently discarded. For others facing a similar problem, here are some things to check:
Check that IPv6 connectivity is working from the gateway computer (ping6 ipv6.google.com or similar).
Check that network computers receive appropriate IPv6 addresses (that radvd or dhcp6 are working properly) and that they can connect/ping to the gateway over IPv6.
Check that forwarding is enabled for IPv6 on all (or at least both local and public) interfaces in the kernel (sysctl net.ipv6.conf.all.forwarding). This can be set permanently in /etc/sysctl.conf.
Check that the gateway computer has an explicit default route. This is important! If an IPv6 gateway address is not specified, traffic will not be forwarded. (Make sure there is a gateway statement in /etc/network/interfaces and/or that route -6 lists a global default route with a gateway address.)
Check that there are no firewall rules blocking traffic and that the default FORWARD policy is ACCEPT (ip6tables -L).
Check that the internal network address of the gateway has a global IPv6 address assigned. A link-local address is not sufficient and Linux will not forward traffic from interfaces with only link-local addresses!
For the curious, it was the last point which was causing my problem. As a reference, here is a snippet from /etc/network/interfaces which I used to configure the tunnel: