You might want to try pinging the link-local address to narrow it down between a firewall or other networking problem between the two hosts, and a Teredo problem. I have heard of problems where, when using Teredo-based IPv6 addresses, you cannot ping other machines on your own subnet. For example, I can ping a Windows 7 machine on the same network as my Ubuntu machine by doing this (on my Ubuntu machine):
$ ping6 -c 5 -I eth0 fe80::e1ce:694a:18c0:6530
Note, the -I argument is important when pinging a link-local address because otherwise the host OS has no way to know which link-local interface you're talking about. (for all it knows, you want to use the Teredo interface, or the loopback interface, for example.)