
to Gimp Chat, Matt!
One thing that may help is to change the resolution of your image. Most are at 72ppi, increase to 300 before scaling larger. Making images larger in gimp doesn't work as well as scaling them smaller. Some of the blurriness can be helped by using Sharpen. Click Filters > Enhance > Sharpen. You can control the amount of sharpening in the Sharpen dialog.
I like to use Inkscape for scaling images. I have written a text tutorial about scaling an image in Inkscape but I haven't put screen shots in it yet. I'll finish the tutorial and post it so you can give it a try.
Here are examples of an image with the resolution changed to 300ppi - a 96x96px image scaled to 200x200px using GIMP and Inkscape.
Neither is entirely satisfactory but the Inkscape scaled image looks a bit better.

You can download Inkscape here:
http://www.inkscape.org/