My suggestion is to save your money. Geniuine Fractals is overrated and overpriced, it's a dinosaur of a product that had its start back in the days when Photoshop's own interpolation routines were extremely primitive. IMHO the results GF produces have a very digital look, which I do not like at all. It tries to preserve edges without increasing noise or pixelation. The result is often an image with overly clean/sharp edges, but completely lacking in texture/detail. You can even see this in the sample on their product page. To me it looks terrible.
If you really want to spend money on up-rezzing software, SAR Image Processor probably has the best routines and is much cheaper. It's not the most user-friendly software though. Honestly, even the standard routines in products like Photoshop are good enough if used correctly, that I don't see a need to purchase up-rezzing software.
My preferred approach for large prints is to up-rez past the target print size using Bicubic Smoother, apply a bit of print sharpening, and then down-rez to target print size using Bicubic Sharper. This workflow technique was originally described in the following Outback Photo article:
http://www.outbackphoto.com/workflow/wf_60/essay.html
Another trick I use on large prints is to add some grain to the image. This helps hide the lack of fine detail/texture and gives the print a more film-like appearance, making it look both sharper and more detailed. It may seem counter-intuitive, but it works.