you need to make sure that the username that you're trying to sudo from is a member of the wheel group, and then you'll need to use 'visudo' to uncomment the appropriate line in the /etc/sudoers file to allow people in the wheel group to sudo. After you get that done, make sure that you are using the USER password, NOT the root password.
If you want to get to a root console from within a user console, you can use the 'su -' command, and then type the root password in order to get a root terminal. Then you can do anything root can do. With this method, you don't have to do any user/group fiddling.
Hope that helps.
Jared