Install does not see gd but it is there (phpinfo.shows it)

Aha, you have a setup with support for PNG, but not for JPEG? The GD-check does not anticipate for this (in image_captcha.module):

function _image_captcha_check_setup($check_fonts=TRUE) {
  // Start clean.
  $status = 0;
  // Check if we can use the GD library.
  // Note that we are only checking
  // for the existence of the imagejpeg function.
  // We could also check for imagepng, which can also be used
  // (optionally) for the image CAPTCHA by the site admin.
  // However, this incurs extra complexity in the setup checking
  // (more constants to define) and in the caller functions
  // (more situations to check for).
  // We take this shortcut (only checking for imagejpeg) because
  // it's probably pretty safe to assume that imagepng
  // is available when imagejpeg is available.
  if (!function_exists('imagejpeg')) {
    $status = $status | IMAGE_CAPTCHA_ERROR_NO_GDLIB;
  }

It would be interesting to know why this assumption (PNG enabled, JPEG disabled) does not work for you.
Can you describe your setup: is in on shared hosting? Did you compile everything yourself?

To be fair: recompiling with JPEG support will probably be the fastest solution for you I'm afraid. I (being the only maintainer currently) have almost no free time to invest anymore in maintenance and development, so fixing this in the CAPTCHA module is pretty unlikely in the short term.

Apart from these practicalities: is there a certain (compelling) reason you didn't compile with JPEG support (patent-related, performance-related, complexity-related, ...)? Or you just forgot at the time?

FYI: here are related issues:
#579080: image CAPTCHA in PNG format: check GDlib's PNG support
#589388: refactor _image_captcha_check_setup() for GD/JPEG/PNG support
and I think this one should be marked as duplicate.