This is a problem with PHP-GD implementation in Ubuntu/Debian systems, you need to recompile the PHP files yourself and fix the patches applied by Ubuntu/Debian to the original PHP-GD package. All steps are described here:
http://wiki.slicehost.com/doku.php?id=php5_with_bundled_gd