Ok now I got it. Sudo shouldn't ask for password though. Check that you have the real sudo (coderus' .deb) and not the fake sudo of qole (if you accidentally replaced /bin/sudo from qole's archive that might be a problem)

EDIT: I can confirm the same error when using devel-su instead of sudo. Try reinstalling sudo from the .deb