You need to update your package lists.
sudo apt-get update
Then try again. That will fix everything.
You see, when Ubuntu software developers write their software, they send it to the Launchpad servers, where they compile and process the code. Once the code has been successfully compiled, the new package replaces the old package, and the package lists are updated to reflect that change.
Note that it's just the package lists on their server, not your computer.
sudo apt-get update fetches the latest package infofrom the servers, at which point your computer processes it.
sudo apt-get upgrade checks the package lists (the ones stored on your computer,) and compares the software in the package list with the actual versions you have installed. If any of your software has a version newer than it listed in the package list, it will download and install it.
sudo apt-get install <PACKAGE> checks your package list for that software. If found, it downloads and installs it.
(note that the package lists do not contain the software themselves - only the name, version, and the URL to download the software.)
Anyway, I hope my little speech helped you understand Ubuntu's package system a little better!