C compiler cannot create executables
A bit of searching and I seemed to need some extra packages, you can fix this with:
$ sudo aptitude install libc6-dev-i386
This resulted in the packages gcc-4.1-multilib gcc-multilib getting automatically installed. This was the fix for me.