Here's how you could achieve slightly better quality:
<?php
// load image
$image = imagecreatefromstring(file_get_contents('http://oi62.tinypic.com/atx1j.jpg'));
// create a true color image of the same size
$image2 = imagecreatetruecolor(imagesx($image), imagesy($image));
// copy the original gif image on to the true color image
imagecopy($image2, $image, 0, 0, 0, 0, imagesx($image), imagesy($image));
// output image
header("Content-Type: image/gif");
imagegif($image2);
imagedestroy($image);
imagedestroy($image2);
?>
Source Image
PHP Generated GIF Image
As you can see, it's slightly better. Very close to orignal. But you are still limited to 256 colors in GIF =[