Bem, você não especificou se os problemas recaem sobre a resolução de nomes, quando o Firefox exibe a mensagem :
Servidor não encontrado

O Firefox não conseguiu localizar www.xxx.xx.
Eu tive este problema, tempos atrás, com o mesmo Debian Lenny 5.0 e provavelmente o mesmo Firefox (ou Icewease, neste momento não lembro se fiz a troca !).

Como não tinha tempo para analisar o problema e tinha urgência, acabei botando o endereço do(s) site(s) no /etc/hosts (aliás, estão até hoje ).
Da mesma forma, a navegação numa máquina Windows ia normalmente.

Assim, conclui que esse problema parece estar associado a resolução de nomes, e no caso, descartei o DNS Server do provedor, já que no Windows não tinha problemas.
Então o problema deveria estar obrigatoriamente no Linux e em especial na resolução de nomes, pois a partir do momento que adicionei os endereços no /etc/hosts, resolvi o problema imediato da resolução de nomes.

Se eu fosse fazer uma analise mais profunda, começaria olhando os arquivos :

/etc/resolv.conf - se este arquivo contiver keywords nameserver com IP que dão timeout isso poderá causar o problema na navegação. O mesmo vale para a keyword search.

/etc/nsswitch.conf - como estão configuradas as keywords e qual a ação tomada em caso de problemas.

/etc/nscd.conf (isso se você tiver instalado o nscd - name server cache daemon e deveria tê-lo !!!) Em máquinas onde há intensa utilização pode ser que os parâmetros defaults não sejam adequados.

Acho que isso poderia ajudá-lo. Espero