the way sudo works is it wants the user password.
The user doesn't have a password by default.

If your sudoers file is hosed and is requesting for a password when using sudo gainroot you're in trouble.

I'd try uninstalling and re-installing rootsh in hopes it can fix it.

The way rootsh works is it sets up the sudoers file to not require a password for "sudo gainroot".. which is what all the the other commands wrap around (rootsh, root, etc).