I'm using a fresh install of Kubuntu 8.04 with KDE3 (though this is not a KDE/Gnome problem). I have installed libc6-dev, make, automake, autoconf, g++, gcc and other things.

Whenever I try to compile something with ./configure, I have problems. It says:

I found a way around this by doing: "sh ./configure" but the configure script fails because it try to execute './a.out' at one point as a check, and gets the error:

This is a fairly serious error, since this means I cannot compile things. Anyone know of this bug and if there is a fix?

Try command: sudo ./configure

Are you trying this in your home directory where you have full rights? Also make sure you didn't untar the tarball using a windows utility. A \n\r pair at the end of lines in scripts can cause problems as well, but I don't think this is the case here.
Also make sure you have the binutils package installed.

The problem was how I had mounted my harddrive. I normally configure my /etc/fstab by hand, but this time I figured "What the hey? I'll just let KDE do it for me through their GUI." Well, the GUI set the drive with 'noexec' as an option when mounting.

I changed the option, remounted and everything was fine.