Pesquisar:

Não é problema de DNS não... Só pra saber se o DNS tava desconfigurado, quando num tem nenhuma configuração de DNS q ele reclama.

Outra coisa, tenta ver se o DNS tá configurado direito nessa maquina. As vezes, como acontece no ssh, quando dns tá desconfigurado ele demora a contectar.

Tu já deu uma olhada no desempenho da maquina quando tá iniciando? Roda um top, nos 10 mins q ele demora pra iniciar.