ну раз замена DNS помогла - вероятнее всего дело в "старом" сервере DNS. проверяйте его.
подозреваю что их у Вас 2, и первый не отвечает, что для Вас выглядит как долгий запрос ( на самом деле запрос к первому висит до таймаута, потом уходит на второй и там резолвится)
