Adding this answer partially because it fixed my problem of the same issue and so I can bookmark this question myself.
I was able to fix it by doing the following:
sudo apt-get install gcc-multilib g++-multilib
If you’ve installed a version of gcc
/ g++
that doesn’t ship by default (such as g++-4.8
on lucid) you’ll want to match the version as well:
sudo apt-get install gcc-4.8-multilib g++-4.8-multilib