Try like this...

Code:
<?php
$type="gif";

if($type=="jpg")
{
    $image = imagecreatefromjpeg('test.jpg');
    $red = imagecolorallocate($image, 255, 0, 0);
    imagefill($image, 29, 45, $red);

    header('Content-type: image/jpeg');
    imagejpeg($image);
}
elseif($type=="gif")
{
    $image = imagecreatefromgif('test.gif');
    $red = imagecolorallocate($image, 255, 0, 0);
    imagefill($image, 29, 45, $red);

    header('Content-type: image/gif');
    imagegif($image);
}
imagedestroy($image);
?>
Like kows said, in your original code, $red was being allocated for $im, not for $image. Why it then worked for jpg and not for gif, I don't know, but this should work for both.