Nothing--no technique, no algorithm, and no program--can take a small image and blow it up without degrading quality. It is not even theoretically possible. There is no way to add detail to an image that does not exist in the original.
Genuine Fractals produces results that are moderately better than Photoshop's built-in interpolation for some images--emphasis on "moderately" and "some images." On some images, the results produced by Genuine Fractals are worse.
Of course, you won't see that in Genuine Fractals advertising. Part of advertising a piece of software is in carefully choosing data that makes your software look best. I used to demo software at trade shows, and we would be very, very careful about the samples we used in the demos. I have known cases were people who are giving software demos will pay their own employees to act like audience members and to ask questions designed to give the person running the demo a chance to show off some particular, obscure data set or procedure that really makes the program look good.
Some images benefit from Genuine Fractals; some don't. In any event, if you blow up an image using Photoshop's bicubic interpolation, you won't see pixels either--the image simply looks soft and slightly out of focus, just as it does with Genuine Fractals. Nothing, however, will ever look as good as simply making the image at the right resolution in the first place!
I became disenchanted with Genuine Fractals, and believed that the company is unethical and practices snake-oil salesmanship, when I saw one of their brochures. The brochure had a lot of pairs of pictures. In each pair, one picture was scanned at high resolution, and one was scanned at low resolution and blown up using Genuine Fractals. The brochure challenged viewers to guess which one was high res and which one was enlarged.
I guessed correctly on every image. However, every image enlarged with Genuine Fractals looked better. Why? Because the images scanned at high resolution were not sharpened. The images enlarged with Genuine Fractals were blown up and then sharpened. Everyone who works prepress knows that any picture printed on a press must be sharpened. The company was trying to skew the results. If they would have sharpened the high-res scans the way they sharpened the blown-up pictures, the high-res scans would have looked better.
People keep looking for a quick fix. There is none. if you want a high-quality image, you must start with a high-quality, high-resolution original. There is no shortcut.