@JuriMarlow
I had the same issue. Make sure your Windows Firewall is Enabled! It will block your server connection even if your NAT is open with the firewall off.
As for how I got my NAT open:
I was never able to re-install the Teredo adapter. However when I checked the state in command prompt using netsh int teredo show state it showed that my NAT was restricted due to the port. I found that this port would not work, even when it had been forwarded through my router.
The solution for me was to change that port to 3544. The easiest way to do this is through group policy editor:
In the run or search box type gpedit.msc
Navigate to: Computer Configuration > Administrative Templates > Network > TCPIP Settings > IPv6 Transition Technologies
On the right side you will see Set Teredo Client Portedit this policy
Change the policy to Enabled and set the port below
Apply and OK and check your teredo state again.
Mine went from restricted to cone, and my NAT is now open.
That port will also need to be open/forwarded through your router. Look up how to do that for your particular router manufacturer.
Hope this helps!