Try this code (changes at lines 2-4):
<?php
$img = imageCreateFromgif("http://cellufun.com/p/avatarimage/agb.aspx?i=Body|M04001|Shirt|M10020|");
$index = imagecolorexact($img, 0, 0, 0);
imagecolortransparent($img, $index);
header("Content-type: image/png");
imagepng($img);
?>
It works for me although it's a little trick ;) ..and I don't know exactly why the quality is worse..
PS: The main problem I see is that the image at the url you provided is not really a png.