If you want to increase the resolution and still maintain image quality, you really have only one choice and that is to lower the physical dimensions of your image. Since you are starting @ 600x600 (this is the same as 4in x 4in) and want a 4in x 5in ouput you are going to lose some thing. What (if i may ask) is the artwork like. You mentioned you should have done it in illus. Is it primarily lineart? If so it may not be to bad... (if you used the vector tools) What's the output device?