Parece um problema de licenciamento no lado da Cisco. Quantos hosts internos você tem licença? Depois de ter atingido seu limite, você não poderá acessar a Internet para hosts subsequentes. Se você executar um sh, ele mostrará quantos hosts internos estão licenciados. Faça um sh local-host e ele mostrará quantos você está usando atualmente. Limpar os xlates (renovar o IP) ou reiniciar o firewall permitirá que os primeiros dispositivos se conectem até que você atinja seu limite.