Назву машини не потрібно повертати на localhost. В лінаксах (в практичній більшості дистрибутивів, якими я користувався) якщо Ви не встановите коретно назву машини, вона залишається localhost. Те, що Ви його виправили -- вірно.
Щодо DNS: що у Вас записано в /etc/resolv.conf?
Попробуйте ще війти в singe user, звідти підняти мережу і подивитись таблицю маршрутизації: netstat -nr. Інший варіант -- прибрати скрипти старту сендмейлу (теж із single user'а), підняти машину і подивитись маршрутизацію звідти.
Спробуйте додати default route: route add default [...] інтерфейс, де в Вас сидить ДНС (eth0 мабуть).