As router I am using Vyatta ...
According to Wikipedia it is based on Debian just like Ubuntu is, and it is specialized for networking. With those properties it definitely should support running a Teredo relay. So how about you try out the steps that works on Ubuntu and let us know, if they work on Vyatta as well.
First of all install the software with
apt-get install miredo. Secondly edit the
/etc/miredo.conf configuration file. The default configuration file on installation is for a Teredo client, and what you want is not a client, but a relay. Here is the configuration file, I use on one of my machines
# Please refer to the miredo.conf(5) man page for details.
InterfaceName teredo
RelayType relay
# Pick a Teredo server:
#ServerAddress teredo.ipv6.microsoft.com
#ServerAddress teredo-debian.remlab.net
# Some firewall/NAT setups require a specific UDP port number:
#BindPort 3545
BindPort 64646
I made three changes. I changed the RelayType, I commented out the ServerAddress, and I added a BindPort. I picked a static port number between 61000 and 65535, just for convenience. It is easier to recognize in packet dumps that way. Finally run
service miredo restart which will stop the Teredo client (which may have been started automatically by apt-get install) and then start the relay.