You're missing the 32 bit libc dev package:
On Ubuntu it's called libc6-dev-i386 - do sudo apt-get install libc6-dev-i386. See below for extra instructions for Ubuntu 12.04.
On Red Hat distros, the package name is glibc-devel.i686 (Thanks to David Gardner's comment).
On CentOS 5.8, the package name is glibc-devel.i386 (Thanks to JimKleck's comment).
On CentOS 6 / 7, the package name is glibc-devel.i686.
On SLES it's called glibc-devel-32bit - do zypper in glibc-devel-32bit.
On Gentoo it's called sys-libs/glibc - do emerge -1a sys-libs/gcc [source] (Note : One may use equery to confirm this is correct; do equery belongs belongs /usr/include/gnu/stubs-32.h)
On ArchLinux, the package name is lib32-glibc - do pacman -S lib32-glibc.