Lo tengo solucionado.
Después de 3 llamadas al servicio técnico de Movistar e intentar actualizar firmware ellos, resetar router, poner ip estática en el Nexus 4....
Al final he localizado una actualización (
http://cdn.redeszone.net/down/firm/z..._AHF.0_b23.rar ) y en un par de minutos solucionado!