I wouldn't necessarily blame eZ Publish: If you're using IE, you must know that IE has notorious problems with PNGs and transparency. First, check if the image shows correctly in a regular HTML file (without any eZ Publish) on your browser. Transparency is a hell to maintain in HTML (just google for 'hack' + PNG) , if you can avoid it, do so.
The image is perfect for "original" image class. but for other classes like small, medium and for .gif transperent images, ez puts gray in image where there is transperency.
OK, it obviously the comes from the transformation: as Łukasz suggests, you should use ImageMagick which is much more powerful than GD. As you said, it is still disabled on your installation.