I don't have g++:

erelsgl@ubuntu:/etc/apt$ which g++
erelsgl@ubuntu:/etc/apt$ 

erelsgl@ubuntu:/etc/apt$ g++
The program 'g++' can be found in the following packages:
 * g++
 * pentium-builder
Try: sudo apt-get install <selected package>

So I try to install it:

erelsgl@ubuntu:~/srilm$ sudo apt-get install g++
Reading package lists... Done
Building dependency tree       
Reading state information... Done
g++ is already the newest version.
0 upgraded, 0 newly installed, 0 to remove and 5 not upgraded.
2 not fully installed or removed.
After this operation, 0B of additional disk space will be used.
Setting up g++ (4:4.4.3-1ubuntu1) ...
update-alternatives: error: alternative path /usr/bin/g++ doesn't exist.
dpkg: error processing g++ (--configure):
 subprocess installed post-installation script returned error exit status 2
dpkg: dependency problems prevent configuration of build-essential:
 build-essential depends on g++ (>= 4:4.3.1); however:
  Package g++ is not configured yet.
dpkg: error processing build-essential (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                                                                                                          Errors were encountered while processing:
 g++
 build-essential
E: Sub-process /usr/bin/dpkg returned an error code (1)

I also try to install build-essential, and get same results.

I also tried "sudo apt-get update" - didn't help.

This is my apt-cache:

erelsgl@ubuntu:/etc/apt$ apt-cache policy g++ build-essential
g++:
  Installed: 4:4.4.3-1ubuntu1
  Candidate: 4:4.4.3-1ubuntu1
  Version table:
 *** 4:4.4.3-1ubuntu1 0
        500 http://il.archive.ubuntu.com/ubuntu/ lucid/main Packages
        100 /var/lib/dpkg/status
build-essential:
  Installed: 11.4build1
  Candidate: 11.4build1
  Version table:
 *** 11.4build1 0
        500 http://il.archive.ubuntu.com/ubuntu/ lucid/main Packages
        100 /var/lib/dpkg/status
erelsgl@ubuntu:/etc/apt$ 

I also tried this and got the same error:

erelsgl@ubuntu:~/Ace/Files/corpus$ sudo dpkg --configure -a
Setting up g++ (4:4.4.3-1ubuntu1) ...
update-alternatives: error: alternative path /usr/bin/g++ doesn't exist.
dpkg: error processing g++ (--configure):
 subprocess installed post-installation script returned error exit status 2
dpkg: dependency problems prevent configuration of build-essential:
 build-essential depends on g++ (>= 4:4.3.1); however:
  Package g++ is not configured yet.
dpkg: error processing build-essential (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 g++
 build-essential