You need the header files, which are provided by -dev packages, and not in the library packages themselves. So, try installing libx11-dev. That should fix this particular build error, though you may get similar errors about other libraries (and then you can install their -dev packages.)
Even though these packages provide header files rather than binaries, and in general header files account for all supported architectures through the use of preprocessor macros, nonetheless -dev packages in Ubuntu tend to be architecture-specific, and this is the case for libx11-dev (as can be seen here by expanding a release and finding the .deb packages listed for libx11-dev in that release). Since your Ubuntu system is 64-bit and you're compiling a 32-bit program which must link against the 32-bit version of the library, you'll probably need to install the 32-bit version of libx11-dev. If you're installing with apt-get or aptitude, you can specify that by indicating libx11-dev:i386 as the package to install (since multarch is supported and being used).
http://packages.ubuntu.com/ is a good resource for finding the name of the -dev package corresponding to a library package. It's not always the library package's name immediately followed by -dev; sometimes version numbers present in the library package name, especially after a -, are absent in the name of the corresponding -dev package.
ldconfig -p | grep libX11\\.? – Martin Dirichs Oct 18 '12 at 19:15