Se hai 'Supporto per IPv6' attivo sul Fritz disabilitalo. Altrimenti, specialmente se l'assegnazione di indirizzi ULA è attivo, il Fritz assegnerà indirizzi IPv6 locali che non possono accedere a Internet, ma l'Xbox potrebbe tentare di usarli.
Per usare un tunnel devi configurare una 'uscita' del tunnel, non è automatico. Ci sono servizi che mettono a disposizione quezte 'uscite', come quello di Hurricane Electric, ma devi ottenere i parametri di configurazione e inserirli nel Fritz. Questi tunnel possono aumentare la latenza, dipende da dove escono e dove devi arrivare.
Teredo stesso comuque è un meccanismo di tunneling IPv6, che dovrebbe essere gestito automaticamente dall'Xbox, se non sbaglio.
Strano che il Fritzbox ti si blocchi disabilitando il filtro Teredo. Nel caso, è un bug del Fritz. Ma lo hai disabilitato con anche IPv6 disabilitato? Non ti serva avere IPv6 abilitato sul Fritz, il tunnel lo fa direttamente l'Xbox.