Apparently apt-get doesn't know about gcc.
If apt-get knows about a package whose name is g++, it won't attempt to to interpret g++ as anything but the name of a single package. (In contrast, I can reproduce the behavior you're seeing by attempting to install the similarly named nonexistent package q++.)
There are two likely causes of apt-get not knowing about the g++ 
package:
- No software source providing
g++ package is configured to be used.
- A software source providing
g++ is configured to be used but the information about what packages are available for installation hasn't been updated since then.
If it were the second reason, you could just run sudo apt-get update. But I think it's more likely the first one.
Make sure main is enabled.
g++ is provided in the main repository component. This should pretty much always be enabled, but perhaps it is not.
Many of the packages necessary for a working Ubuntu system are provided by the main component (this is the software maintained directly by Canonical rather than by the larger community, and it consists mostly of core software important to many Ubuntu systems). Furthermore, some of the packages apt-get listed as installed, such as python-gconf, are in main.
So I think what happened was that main got disabled recently, probably by accident. apt-get knows about software from main that is currently installed because it can see that it's installed. But if main is disabled, apt-get doesn't know about any software from main that you don't have.
To check if main is enabled, and re-enable it if it's not, open Software & Updates (called Software Sources on previous versions of Ubuntu). One way to open this is to click the Settings... button in the Software Updater (called the Update Manager in old versions of Ubuntu).
Then make sure the box labeled "Canonical-supported free and open-source software (main)" is checked.
If it already was, then most likely I have guessed wrong about the cause of your problem. If it was not already checked, check the box (you may need to enter your password) and click Close. You'll be told "The information about available software is out of date"; click the Reload button.
Then try installing g++ again.
Try a different APT mirror.
If the main component was already enabled, maybe there's something wrong with the APT mirror you're using. Especially if you're not using one of the official mirrors (us.archive.ubuntu.com, with us replaced with your "country code"), I recommend trying a different mirror, an official one if possible.
You can set your APT mirror in Software & Updates as well. Just change it in the drop-down menu labeled "Download from".
As when enabling a software source, when you quit Software & Updates after changing your download server, you'll be prompted that software information is out of date and you should click Reload. Then see if g++ can be installed.
Further troubleshooting.
If it still can't be installed, then you should edit your question with more information to help troubleshoot the problem.
- Provide the contents of
/etc/apt/sources.list. One way to do this is to copy the complete output of the command cat /etc/apt/sources.list and paste it into your question. Select it and press Ctrl+K to format it properly.
- Optionally, you might want to see if you can find and install the g++ package in the Software Center. If you can, great! More likely, maybe doing so will reveal some information useful to figuring out what's wrong.
