O firewall estava restringindo o acesso à internet. Se você estiver usando a versão GUI do firewall, é tão simples quanto abrir o firewall e desabilitá-lo. Isso deve resolver todos os problemas.
Eu configurei um hotspot usando o hotspot do Access Point, e meu telefone Android está conectado ao hotspot, mas não consigo acessar a internet pelo telefone, embora esteja conectado. Eu uso o Ubuntu 14.04
O firewall estava restringindo o acesso à internet. Se você estiver usando a versão GUI do firewall, é tão simples quanto abrir o firewall e desabilitá-lo. Isso deve resolver todos os problemas.
Sudheer: para que a navegação na Internet através de um hotspot funcione, você deve habilitar o encaminhamento no hotspot e configurar o NAT em seu firewall.