Eu tenho o Ubuntu 12.04 e faz alguns meses que tenho esse problema.
O problema é que as configurações de proxy do firefox não têm efeito sobre ele e, apesar das configurações definidas em Edit->Preferences->Advanced-Network->Settigs , ele sempre se conecta diretamente à Internet. Configurar por FoxyProxy extension também não funciona.
Até mesmo definir as configurações do sistema ( System settings->Network->Network Proxy->Apply system wide ) não tem efeito.
Outros navegadores como o Chrome funcionam bem.
Informações do sistema:
Ubuntu 12.04 LTS de 64 bits
Firefox 26.0 (eu tive esse problema em 25 também)
RESOLVIDO: não sei porque, mas depois de correr sudo firefox o problema desapareceu!