Funcionó (tras varios intentos) solamente borrando datos del marco de servicios, sin forzar parada. Tanto en mi N4 como en N7, ahora los dos con 4.3 y feliz.
Aunque tuve que borrar y añadir de nuevo mi cuenta de google porque el market no me descargaba