Quero agradecer a ajuda recebida aqui no fórum, em especial ao zekkerj, pela paciência e dicas prestadas.
Como solucionei o problema?
Fiz uma instalação limpa da versão 10.04 onde tudo funcionava sem problemas e depois fui atualizando até à versão 11.10 via Gestor de Atualizações.
Desta forma, e nos últimos dois dias não tenho tido problemas com as ligações à internet.
Grato pela simpatia de todos,
Atenciosamente
André Carvalho