If you are using the Terminal to update software in Ubuntu, you need to run both the Update and Upgrade commands. The Update command updates the list of available packages, whereas the Upgrade command installs the newer versions of the packages just downloaded.
$ sudo apt-get update (Wait for the packages to be updated, as this executes).
$ sudo apt-get upgrade
As you know, sudo lets you update and install packages as root.