¿no hace falta conectar el cable de teléfono que te trae el portátil a la linea teléfonica? ¿Se supone que tengo que poder acceder a Internet sin necesidad de conectar nada?
Efectivamente, no hace falta. Prueba a bajar el nivel de seguridad del firewall y, en todo caso, mira si el router tiene algún botón para permitir que otros dispositivos se enlacen a él (activar el DHCP por ejemplo)

¿Tienes la clave wep a mano no?

Es extraño, pues con el Vista y XP recien instalados, el mismo portatil a mi me dice que hay redes inalámbricas disponibles y se conecta automáticamente (previa validación wep).

Fijate si el PC que tienes conectado al router y el router tienen direcciones IP similares, y si en el portátil después de conectar tienes tambien una IP parecida. Por ejemplo:

Router: 192.128.1.1
PC Conectado 192.128.1.10

Portátil por conectar: 192.128.1.x

Inténtalo a ver si funciona