As Telos quite rightly says, enlarging digital images with little or no loss of quality is difficult. This is because a digital image only has so much data held within it, so whatever image-processing software you are using to enlarge the image has to supply data to "fill in" the inevitable gaps that result. I have not used PSP for many years, so I don't know how good its image-enlarging algorithms are, but I would recommend you use "Resample" rather than "Resize" if you're doing it within the application.
There are a number of 3rd-party plugins and stand-alone applications that claim to be able to resize images with little loss of quality. I have tried a few of these - one of the best is Alien Skin's
Blow Up, but unfortunately I think that's only available as a Photoshop plugin. Another good one is
PhotoZoom Pro, which is available as both a Photoshop plugin and a standalone application. It's effective, but unfortunately not cheap.
Apparently the industry standard is
Genuine Fractals Print Pro, although I haven't tried this (and it's also very expensive at $299.99 for the full app).
There are, however, some free applications (such as
PicuSizer) - although again I have no experience of how good (or otherwise) they are.
You can find links to lots of image-resizing applications here:
Enlarge Image Software