The title of this post says "6to4 (NAT traversal)". This is fundamentally impossible. It does not work on your standard Linux, let alone Android. The 6to4 protocol relies on having a public IPv4 address on the same machine you terminate the tunnel on.
Leaving that aside, it may be that you are simply using the word "6to4" when in fact you mean "IPv6 tunnelling". Other tools, such as AICCU or gogoc, utilise different protocols that encapsulate IPv6 within UDP within IPv4 to allow the NAT traversal to work. These do not use 6to4.
Your Android distribution must support the necessary kernel modules for tunnelling to work. You must have the
sit module available for 6to4 (or the
tun module for many VPN products, and so on and so forth) as well as the ability to add tunnels such as via
ip tunnel add mode sit. It may be that you do not have that available.
I have a device (Motorola Milestone running CM7) that is supported by the IPv6Config app you mentioned above. The app does not appear to do anything phone-specific. I suspect that the fundamental problem is that simply having "root" on your phone is not enough — your Android must ship with the appropriate kernel modules.
You may need to run another distro (e.g. CyanogenMod instead of a rooted stock Android) that includes the proper support to allow such tunnelling to work.