Таки обошелся без переустановки сервера :)
Проблема крылась в настройках клиентов -- resolv.conf.
В настройках сетевого интерфейса был прописан DNS-сервер сервера, из-за этого и не проходила регистрация пользователя. Заметил совершенно случайно. Не знаю баг это или нет, но сейчас без него работает. Оставил только DHCP.
Огромное спасибо Skull за помощь! ;)
P.S. Хоть я и не топик-стартер, но, думаю, можно поставить теме статус решено :)