I've run into the same challenge, and I still haven't found anything that works magic. However, you can sometimes get pretty good results by resampling upwards in increments of 10% - in other words, if the original is 72ppi, go to about 80ppi first, then roughly 88ppi, etc. The Image>Resize>Image Size box also has an area in which you can choose to resample by percentage. I've never used that (the easy way!), I just always go with what's harder and longer. My basic nature, I guess.
There's another plugin called Genuine Fractals. It's also very expensive to buy, but they do have a demo version that can be downloaded and used about 10 times, I think. You might try that. In either case, first make a copy of that original before you start playing with it and also make sure it's been converted to a non-lossy format if you haven't done that already.
If you do find anything magic, let us know!