gifs can't be made without the hacked gd lib. [1.3 i think].
It sucks but blame unisys (i think they own gif these days)
There is tons of info out there on why you shouldn't use gifs so maybe you should make a note to your users on why they can only use jpegs and pngs on your site so that maybe they will consider using something else too. (btw...jpegs and pngs are really a better format for photos...gifs are a little better for graphics but most folks digi cameras will dump to jpeg anyways)
Of course you can always find the hacked gdlib out there if you look hard enough.