Já estou quase desistindo dessa história, mas não custa tentar:
Recentemente me mudei, e aproveitando a mudança, troquei a Brasil Telecom pela Net (Virtua).
Antigamente nós tínhamos a seguinte conexão:
Linha DSL --> Modem --> Hub --> PC1
\---> PC2
E o modem dava conta de distribuir os IPs corretamente. Ele próprio ficava com o IP externo da conexão 201.x.x.x e os dois PCs ficavam com IPs internos; no caso, eram 192.168.1.x.
Agora com a Net temos um problema, porque o modem, aparentemente, só funciona no modo bridge (é um Motorolla Surfboard).
Com o hub, o primeiro computador a se conectar ganhava o IP externo, e o segundo não recebia nada (a requisição DHCP esgotava o tempo).
Então meu pai trocou o hub mais um AP wireless por um roteador já com wireless da DLink, um DSL-G604T, mas o problema persiste. A única diferença agora é que o primeiro computador a ligar fica com o IP externo e o outro fica com um IP interno, 10.1.1.x.
Mandei um email para a DLink, eles disseram para desligar o servidor DHCP do DSL-G604T, mas não adiantou nada.

edit: lembrando que agora a conexão é a cabo, e não DSL.