Los firmwares de los routers actualmente indican claramente cuando están conectados correctamente a Internet.
Si ese fuera el caso de tu router y ya la conexión entre el mismo y el módem está bien, tendrías que pasar a enfocarte en la conexión a las dos máquinas: los cables de conexión tienen que ser correctos, como te dijo Quicksilver88, tienen que ser lineales entre el router y las PCs.
Suponiendo que está todo bien, tendrías que pasar a concentrarte en tener bien configurada la conexión en cada PC, de acuerdo al Sistema Operativo que tenés.
A mí me pasó en XP, por ejemplo, que tenía todo bien conectado y pese a que tendría que haber detectado todo "automáticamente"

hasta que no armé conexiones nuevas en cada una de las PCs bien relacionadas a las placas de red correspondientes, no funcionó nada.
En el caso que uses Win, fijate si creando conexiones nuevas se soluciona el tema en el caso que tengas todo bien. También chequeá que no tengas problemas de configuración con tus placas de red.
Si usás Linux, no tengo los conocimientos para ayudarte. Sin embargo te cuento que con un Ubuntu Live CD la conexión me funcionó antes y mejor que en XP.
Ahí sí detectó todo automáticamente y sin problemas... Así que quizá también te podría servir como un test si para vos ya tendría que funcionar todo bien y descartaste el resto de los factores.
Saludos!