You can solve this by configuring Miredo (via /etc/miredo/miredo.conf) to use a Teredo server that actually works – various providers have been shutting down their Teredo servers and relays due to increasing availability of native IPv6. I can't seem to find the relevant mailing list posts right now, but Microsoft has been trying to shut down theirs since ~2012.
(There are also repeated claims that Teredo just generally does more harm than good – the relays are often slower than IPv4, the addresses are dynamic so useless for incoming connections.)
One out of remaining Teredo servers is teredo.remlab.net, from the Miredo developers.
Of course, also make sure your network's firewall allows Teredo traffic – the servers listen on UDP port 3544 for the "binding" messages, while relayed traffic usually uses a somewhat random UDP port number.