There are actually two mechanisms set up in Ubuntu for performing administrative tasks. sudo is one of them, and it and its graphical frontends (like gksu and gksudo) are not going to work until you fix the permissions problem.

The other mechanism is PolicyKit. Depending on exactly what you have done to your file permissions, it's likely that you can still recover using PolicyKit to run commands as root.

The pkexec command will run any (nongraphical) command as root (provided that the user invoking it is an administrator on the system). pkexec is capable of running graphical commands (like nautilus) as root, too, but this is quite nontrivial, as you have to set up configuration files for them describing how they are supposed to be run and what they are supposed to be allowed to do. Therefore, you're best off using the command-line to fix this problem...at least to the point where sudo works again. (Then you can run gksu nautilus to get a root file browser, if you're more comfortable using that to edit file permissions recursively.)

I don't know exactly what you did to your permissions, so it's hard for me to give you a specific pkexec command to run, to fix the problem. But you can rectify the specific problem that sudo is currently complaining about. It says:

sudo: /usr/lib/sudo/sudoers.so must be only be writable by owner

So remove group and other write permissions (while not modifying owner write permissions) for that file:

pkexec chmod go-w /usr/lib/sudo/sudoers.so

Then you can see if sudo works (by running some innocuous command like sudo ls).

If you need to perform other operations on file permissions from the command-line with chmod, see man chmod.

(By the way, here's another, related situation where it's handy to know about pkexec.)

If you have trouble getting pkexec to work for this, please feel free to comment here, and I'll try to render further assistance. But you should know that even if this method does not work, you shouldn't have to reinstall Ubuntu.

Instead, you can fix the problem from an Ubuntu live CD/DVD or live USB system, because the live system will be functioning--sudo will work on it--and you can mount your Ubuntu partition and change the permissions that way.

Or as a third option (as forestpiskie has suggested), you could use recovery mode.