Just thought I'd kind of promote this topic a bit, as it was helpful to me and may be helpful to others:
http://www.tunnelbroker.net/forums/index.php?topic=1504.0
I encountered this issue when I decided to move my router from a test VM to a hardened production VM. Used the same config files (/etc/network/interfaces, /etc/radvd.conf, etc.), same IP address, etc. So, the new router should have just come up (tested rebooting on the test router).
I have two 6to4 tunnels - one internal to our WAN (tunneling across an IPv4 VPN), and one to HE. The internal tunnel came up fine, but the HE tunnel didn't. Showed as active on the firewall (forwarding protocol 41), but no joy on pings.
After reading the above article, went to my firewall, flushed ARP (that wasn't the problem), and flushed connections (that did it), as there was an old connection to the test VM in place, apparently.
Problem solved. Thanks!
-- Bill