G++ compilation error "cc1plus" not found

You need to run sudo apt-get install --reinstall g++-4.6. Just reinstalling the g++ package won't work, as it's a meta-package which simply depends on the versioned packages instead.

In Ubuntu, the g++ package is a 'dependency package' that installs the default version of g++ for your OS version (e.g. g++-4.6 for 12.04) so reinstalling the g++ package may not re-install the files you deleted - you probably need to reinstall the underlying g++-N.m package.

You can find out what the actual default package is by executing apt-cache depends g++ or by following the g++ symlink using ls -l $(which g++). Alternatively you could use readlink to follow the link automatically e.g.

sudo apt-get install --reinstall $(readlink $(which g++))