I managed to solve the problem. It was definitely the cross-compiler. I switched to the gcc-4.6-arm-linux-gnueabihf (hard float) compiler available through the debian repository as described by
christian-hoff (scroll down to "Compiling Kinde 5 kernel").
If anyone has any idea why the hard float compiler works while the soft float compiler fails to produce a bootable image, I'd be very interested!
Also, if someone has a crosstool-ng config file that is known to work for compiling kindle 4 kernels, I'd really like a copy of that
