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

The -m32 is telling gcc to compile for a 32-bit platform. On a 64-bit platform, gcc normally only comes with 64-bit libraries. You have two options:

1. Install 32-bit headers and libraries. Here's how you'd do this on Ubuntu.

   Run this command:

   sudo apt-get install gcc-multilib
   

2. Compile for 64-bit instead. Modify this line in the file named configure:

    CFLAGS="-m32 -ansi -D_SVID_SOURCE -DOSS_AUDIO -D'ARCH=\"$host_cpu\"' $CFLAGS"
   

   Delete -m32, giving you:

    CFLAGS="-ansi -D_SVID_SOURCE -DOSS_AUDIO -D'ARCH=\"$host_cpu\"' $CFLAGS"
   

   Run ./configure, then make clean, then make

   However, I would recommend against this approach. The library authors went out of their way to make this build for 32 bits on a 64 bit system, and I can't guarantee that it will work correctly if you do this. (It does compile, though.)

The 64-bit bits/c++config.h file is provided on 32-bit systems (and vice-versa) by installing the g++-multilib package, so you need to install that package either using Software Center, Synaptic, or via the terminal using

sudo apt-get install g++-multilib

This is just a dependency package that resolves to g++-4.8-multilib for the default gcc/g++ version, and in turn depends on lib64stdc++-4.8-dev (64-bit compilation on 32-bit) or libx32stdc++-4.8-dev (32-bit compilation on 64-bit) - it is these that contain the actual header files.

There is an equivalent set of packages for the plain C compiler gcc.

Alright I found out what was the problem:
When I found out, I had to use g++-multilib I went ahead and searched for that in my package manager (synaptic in my case). That one listed a bunch of versions so I checked what version of g++ I had installed and then I installed the appropriate g++-multilib-package which in my case was the g++-7-multilib.

However what it didn't install was the gcc-multilib package which appears to be the troublemaker in my case. After having installed that one, it worked as expected.

Long story short: If I had installed the g++-multilib (without a version in the name) package to begin with, I wouldn't have had this problem.