Is GD definitely working, you aught to check phpinfo() to make sure.
Yes, definetely. (Also checked gd_info() successfully.)
Try $wgUseImageMagick = false; The default settings file has this as false already but it might have been changed
Done. No effect :-(
Does it display empty image placeholders where the thumbnails should be?
IE: empty image (red "X") Firefox: nothing to see
Do the full size versions work when you click on the image?
Yes.