Como você está tentando fazer o login? Do terminal, ssh, X (GDM / KDM / XDM / etc)?
Você já tentou su ing fazer root a partir da conta de usuário?
Ter uma senha root definida, mas não conseguir acessar o terminal como root ou su ing como root, indicaria um problema. Não conseguir logar no X ou via ssh como root seria mais provavelmente o resultado de boas restrições de segurança padrão. Se su funcionar, mas você ainda quiser sudo , poderá executar apenas su -c visudo e, depois, adicionar sua conta de usuário ao arquivo sudoers.