Reputação muito baixa para fazer um comentário versus resposta, mas você verificou se há listagens de dispositivos duplicadas no Network Manager?
Se o seu e-mail funcionar e outros serviços, possivelmente você não tem o mesmo problema que eu tive, após atualizar para o 16.04, com entradas duplicadas na GUI do Network Manager. Essas duplicatas não foram configuradas de acordo com a configuração da minha rede e, portanto, causaram problemas.
Para resolver, eu apaguei todos os dispositivos, reiniciei e configurei os dispositivos descobertos corretamente para as necessidades de proxy da minha LAN.