Try Photoshop, it is great my teacher had a tiny photo very old, he scanned it into photoshop and then used photoshop to blow up the image. And it was great quality.
I don't know about upscalling a .gif, however, there are products out there that will upscale an image (.jpg, .psd, .tiff, etc) such as the well reviewed Genuine Fractals 4.1 http://www.ononesoftware.com/detail.php?prodLine_id=2 The program is not cheap, however, it does what you want it to do, and does it very well. There is a demo to see if it meets your needs. (Demo can be found in the support page of their website). Again, I do not know if will work on .gif extensions.
