Algo semelhante aconteceu comigo.
Por ter sido comprado no exterior, o laptop que eu estava usando tinha um hardware Wi-Fi que suportava menos canais do que os suportados pelo AP (que era local). O AP foi configurado para escolher automaticamente o canal, dependendo das outras redes presentes na área.
Escolheu um canal que não era suportado pelo laptop. Descobri isso usando sudo iwlist eth1 channel
que exibia menos valores (de 1 a 11 apenas) enquanto o AP exibia mais possibilidades (de 1 a 13, a interface da Web mostrava esse detalhe).
Felizmente, eu pude forçar o AP a usar um determinado canal que era suportado pelos dois lados através de sua interface de configuração, tudo funcionou bem depois disso.
Desvantagem: agora, se muitas pessoas estiverem usando o canal que eu escolhi, o desempenho da rede talvez seja afetado.