I ran into this recently and thought it was worth a post. During the Pwnium CTF I was trying to run some of the programs on my Kali VM/partition, which is an amd64 install. Unfortunately the binaries were for the i386 architecture. I did a quick search and all I could find was to run dpkg --add-architecture i386 and install ia32-libs.
. This doesn't play very nice with Kali and requires about 800MB of extra packages. Not so great. So I was searching around again today as I was upgrading Kali to 1.1.8 and found the better answer:
dpkg --add-architecture i386 apt-get update apt-get install libc6:i386
After I did that i386 programs would run. The best part, though: only 11MB. Big improvement, same result. Neat.