I've been working on getting a teredo server working and also on getting the clients configured. Its been an interesting experience working around the different NAT types. I don't have a cheap NAT/PAT router in my lab at home so its been tough doing the required testing for Teredo since almost all my configuration are Symmetric, you'll see why this is an issue in a bit.
As an overview, the different NAT types are:
Cone - basically when your internal host pokes a session out to the Teredo server any other external IP address traffic sent to your external IP's outbound NAT port will be allowed in. Not exactly super secure.
Restricted - when your host pokes a session out it is keep track of one side of the session IP and port along with either the IP and/or port of the other end of the session. Most default Cisco router NAT configurations do this.
Symmetric - NAT devices keeps a full matching rule for internal source IP and port to external source IP and port. Most common to firewalls and more advanced NAT devices that perhaps are doing SPI or other filtering.
Vista clients can work with all three NAT types with one condition, that both hosts are not behind symmetric configurations. Windows XP and Server 2K3 don't work with symmetric NAT at all at this time.
If you are trying out Teredo for the first time point your client at teredo.ipv6.microsoft.com to see if you get an IPv6 address starting with 3ffe:831f. If you do, then you have a configuration that can work with Teredo.
Remember, the netsh command line syntax is different for XP compared to Vista. For Vista you need to run:
netsh int teredo set state client teredo.ipv6.microsoft.com
For XP you need to run:
netsh int ipv6 set teredo client teredo.ipv6.microsoft.com
Now I just need to go buy that cheap wireless router to test some of these NAT situations.