Resizing Cartoon-like Images

So I wanted to make some icons from one of the earlier Disney movies, The Black Cauldron, and whenever I try to resize the screencaps that I use, the outside edges of the picture turn blurry or pixely.

Does anyone have any ideas of how to make it look better? :P

HERE is one of the images.

All help is appreciated!

I use PSP, by the way. :]