Yo ayudarte en si no se si puedo pero te comento mi caso.
Yo tengo un Samsung Galaxy S II (terminal con Android que permite poner el movil en modo punto de acceso, es decir como router usando la conexión 3G) y también tengo Vodafone, en mi caso Vodafone prepago y tengo una tarifa plana ilimitada por la cual pago 0,50 € al dia.
Pues bien cuando pongo el móvil en modo AP y conecto la Xbox al live, al hacer la prueba de conexión al live también me dice que tengo un valor de MTU demasiado bajo, pero aún asi, me puedo conectar al live igual, es más, la conexión me va perfecta y rapidisima...
Has probado a conectarte a el live??
O simplemente has hecho la prueba de conexión y al ver que te daba el error lo has dejado?