@Gmfd973,

So the Teredo Issue is Involved with a NAT issue - to start:

Ensure you only have One Router on your network, if you have more than one, the secondary routers must be placed into Access Point Mode. Next check to see what the UPnP Setting is on your router, this setting is commonly used by consoles to help automatically assign ports. Lastly, is there more than one console on the network, as this can potentially cause issues when both are online. Otherwise, I recommend looking at the Xbox Support Site for Questions Reagrding NAT Errors as they provide very thorough guides for troubleshooting.