That line looks fine, and as long as you used visudo to edit /etc/sudoers the changes should have stuck.
You also need to ensure that the binary at /usr/bin/sudo has the correct permissions - by default they are not set correctly for security reasons.
I have permissions of 4111 on /usr/bin/sudo and this seems to work fine - you certainly need to make sure the 'set UID' bit is set (the 4) otherwise things won't work.
As for the /etc/sudoers entry, you might want to try using:
Code:
user ALL=(ALL) NOPASSWD: ALL
if you feel brave. I use this for one user, from whose account PHP scripts are run to update content within other accounts. For this reason, I need it to work without having to enter the root password.