Después de darle 100 vueltas y hacer todos los tutorials posibles no conseguí hacerlo funcionar. Al final lo solucione haciendo una instalación limpia de Windows 8.1. Ya lo tenia pero simplemente lo había actualizado desde Windows 8 que ya venía de Windows 7 y no me funcionaba.
Al desinstalar todos los drivers y controladores y que el sistema los buscara solo parece que se me soluciono el problema. Ahora me reconoce tanto el nexus 4 cómo el 7 (2013) tanto en depuración como sin ella.