Wayne mentioned the one Photo Zoom Pro, there is also Blow Up from Alien Skin, and Perfect Resize from OnOne. We have the OnOne suite and I use Perfect Resize a good bit as well as Blow Up. All 3 work very similarly and depending on the original one will often have slightly better results than another. It really depends greatly on the image to begin with though but very often you can easily get a 400% enlargement that still looks excellent. But if you are trying to give it garbage to begin with then well, garbage in = garbage out.
You can always go the Photoshop route - in that scenario do not try to adjust the image size all at once. Do it in 5% increments using bicubic (or bicubic smoother). Going in smaller increments will give you a much better result than going at it in one shot. The programs above though will almost always do a better job since they are designed specifically for enlargements and have specially designed algorithms for doing so. I think most use fractal mathematics to pull it off. They do have a cost though. The full OnOne suite - you can often catch it on sale (like right now for 2 more days) for as little as $80 for the full standalone version or $150 for the full version with plugins for all your design programs like PS and Lightroom. The whole suite is really a great deal for the price (we have the full premium). You get some other filters/tools that are really very well done in addition to just Perfect Resize which is excellent on it's own. As often as we are doing very large prints it is pretty much as required tool for us.
