Why does sudo not add root's PATH with Ubuntu 12.04?

Have you looked into the man page for sudo? In the section SECURITY NOTES they talk about how sudo uses the PATH variable.

You also want to look into /etc/sudoers as the PATH can be changed there with secure_path. Settings can also be done by files in the directory /etc/sudoers.d/.

It is suggested to make changes to your sudo configuration by creating files in /etc/sudoers.d/ because then your changes will remain independent of changes to /etc/sudoers that might occur when upgrading sudo to a new version. You should still use the visudo command to create and edit files in /etc/sudoers.d/.

Besides security reasons (as Anders has referred to), keeping the original user's PATH also conforms to the Principle of Least Astonishment.

Suppose you run a program called foo, but discover that you really need to run it as root. So you run sudo foo. It would be bad if the program run by sudo foo is different from the program run by foo, which would happen if there's a different foo in root's PATH. This would fundamentally violate your expectations and the general assumption that sudo does the same thing as what you put after it, except as root.

That's what would happen if sudo prepended root's PATH to your PATH. But suppose sudo appended root's path to your PATH. If this was sudo's behavior, then you'd probably assume that if you can run a program (call it bar) when simulating an initial root login shell (sudo -i), you could also run it with sudo bar. But that assumption would be wrong, because there might be a different bar in your own (i.e., not root's) path.

Rather than sudo's behavior changing from one Ubuntu release to another, what probably happened was that your PATH changed. If you add /sbin, /usr/sbin, and /usr/local/sbin to your PATH, the problem will be solved. Unless you only want sbin in your PATH when running programs as root. In that case, I recommend posting a separate question about that (though one technique for accomplishing this is hinted at in Anders's answer.)