Warning, wild guess ahead: Did you install some other root-enabling package like sudser, open-ssh or other before, so that sudo gets modified somehow to ask for a password?