It depends on the techniques you used in the original. Some upsizing is easily unpixellated, and some is not. I deal with low-res graphics at my day job, so I have some techniques.

One technique that I use a lot, I call "melt." It consists simply of blurring and then sharpening an image. The final effect is to smooth off those rough, pixellated edges. Unfortunately, it also smooths corners & sharp points, which you might need to repair afterward.

Adding noise can also help a lot in making pixellation less noticeable. (It mitigates JPG artifacts, too.)

There is also a fractal upsizer that you might look into. You might find a demo. Sorry, I can't recall the name.