Hard to say. Mabye a Teredo/Miredo Relay is overloaded, or went away completely. That's an disadvantage of teredo/miredo: the service is not provided by one clear provider, but by Servers and Relays across the Internet.
Are all destinations slow over IPv6? Are you using all three IPv6-enabled newsserver:
You could consider getting an IPv6 tunnel from a tunnel like Hurricane Electric, or Sixxs.
Or ... ask your ISP to provide native IPv6. If they can't, you could consider switching to an ISP that provides Ipv6, so for example Xs4all. FYI: my ISP Telfort is providing native IPv6 to me in a pre-pilot. Works great.
Feel free to talk about anything and everything in this board.