I've made a 30x40 print from a 5 megapixel image.
I made very little image preparation, as the image was already more or less optimal. It was one of my older shots, back when I settled for in camera sharpening. The setting I used wasn't aggressive, and serves my purposes nicely. A small contrast and brightness adjustment was made.
I used Genuine Fractals to make it large enough for a 30x40 print. Although more megapixels tends to better, the most important thing is an image that's free of noticeable artifacts and noise (especially when it comes to point and shoots, low ISO is critical... noise reduction programs are also effective to a degree)
Genuine Fractals 4 is an excellent plugin. If I'm not mistaken, you can currently download it from lizardtech.com... fully functional, for a limited amount of enlargements. There's some criticism here and there about it not living up to its claims. I've done my own tests with Adobe CS bicubic(one step adjustment and 10% increments), S-spline and Lanczos interpolations, and I've found Genuine Fractals to be the absolute best in preserving the colors and detail. One strength of Genuine Fractals is that the edges of details remain better defined than any other method. The images may appear very "geometric" or fractalized at 100% magnification, but this isn't noticeable at print resolution.
S-spline was the second best interpolation method... and I would use it over bicubic any day... that is, if I didn't have Genuine Fractals!