I had a very similar experience. After years of faithfully backing up to .Mac, I actually needed to recover my data and Backup ran for hours without accomplishing anything. No error message, but no recovered files either. After three attempts of 8 or more hours each, I finally went to the Genius Bar for help.

The Apple Genius ("That's only my job title, and not an actual description.") blamed the problem on my numerous incrementals. He said that Backup needs full backups every so often to work reliably. He suggested weekly. Gee, it would have been nice to roll that into the program.

HERE'S THE GOOD PART:

The files created by Backup are actually bundles, which means you can 'cd' into them from the command line. The directory structure within the bundles mirrors the directory being backed up, though it is a sparse tree. A given incremental backup only contains the files that were changed. It didn't take much work to whip up a Python program to copy files out of each bundle, starting with the earliest. If I could perform the recovery with well under an hour of coding and no prior experience, why couldn't Apple do it with years of development time?

Of course, my less-frequent full backup made with rsync worked flawlessly.