problema con cable de red

Varias cosas que pueden ser:
1. Tienes que comprobar si la velocidad del modem -> cable de red -> tarjeta de red, sea la misma (10/100).
2. Algún problema de la compañía que te provee internet (aunque supongo que si estás conectado es porque el problema es de tu pc)
3. Fallo temporal de algún registro, que se solucionaría al reiniciar el PC.

Para la primera, prueba dirigéndote a el administrador de dispositivos (puedes acceder mediante el panel de control, o apretando el simbolo de windows del teclado + la tecla pausa al mismo tiempo). Te diriges a continuación a adaptador de red, busca tu tarjeta de red , te diriges a propiedades y en la pestaña de opciones avanzadas, busca la opción Velocidad o Duplex o algo parecido, y si está en: Full Negotation, colocala en 10 mb FULL y si no funciona 100 mb Full. (Si no funciona con ninguna, trata con Half y si tampoco funciona, vuelve a Full Negotation).

No hagas ningún cambio más porque sino puede que tu tarjeta deje de funcionar y sería más complicado reestablecer las opciones.

Todos los windows tienen administrador de dispositivos xD, tengo el Windows 7.
Como tu dices, el cable anda perfecto así que es algo que está fallando en tu otro PC y lo más probable es que sea la velocidad de conexión que reconoce. (Del momento que se queda buscando, es porque también reconoce el cable, porque sino saldría: El cable de red está desconectado)
Si dices que restauraste el sistema, puede que se haya cambiado alguna configuración y ahora esté mal la velocidad de conexión de la tarjeta. El problema comenzó junto con la restauración?

Para administrador de dispositivos, por lo menos en Windows 7, puedes irte a Panel de Control > Hardware y Sonido > Administrador de Dispositivos.
Y lo otro, trata con un cable diferente (no quiere decir que el cable esté malo, pero otro puede estar usando la velocidad que usa su tarjeta de red).