Sometimes, the only way to fix a not-so-great image for enlargement is to give it the "artsy-fartsy" treatment. I other words, instead of using a straight photo, make it an illustration based on the original pic. If you cant fix the flaws in what you have, make them look intentional, hahaha.
Another great filter for doing nice fixes on photos is the Optik-Verve Virtual Photographer set. It is one of the most amazing filter sets I have ever downloaded, and its free. I'd have gladly paid green cash money for it.
Its basically a collection of exquisite photographic darkroom/printing effects simulators, all fully tweakable from within the dialog box.
http://www.photos-of-the-year.com/vphoto/
It comes loaded with an impressive collection of pre-sets, and there are more available for download from that same site, but for some reason I can't seem to find the "user-submitted pre-sets" page, good luck.
I agree very much with a previous post that suggests Xero, a wonderful FREE filter set as well. Between these 2 filters, you should be able to turn just about any less-than-perfect photo into a wonderfully stylish illustration.
A great method for enlarging a too-small source image was recently gleaned from Kelby's Photoshop CS for Digital Photographers; Image> Image Size> instead of inches, PERCENT> 110; Bicubic smoother.
Do this in increments of 110% until it is the size you want, THEN apply your "photo to illustration" filters.
You should be able to transform just about any image into a stylish, moody illustration by tweeking the contrast, boosting the color, (or desaturating it) adding some artsy grain, and softening the focus.