Are you saying you backed up to a PGPDisk, or to a WDE'd external drive?
Large PGPDisks are notoriously easy to corrupt - when that happens, you're essentially out of luck.
If you're backing up a PGPDisk file to Time Machine, you MUST unmount it prior to the backup running, otherwise you'll likely end up with a corrupted backup of that file.
You may also have run into basic issues with Time Machine - it appears that 10.6.6 changed the TM code, and it either corrupted backups, or does a better job at detecting them. Both my machines lost their TM backups within a week of the upgrade, and many others at my company have experienced the same thing.
In any case, and it may be too late, it's always a good idea to have at least on unencyrpted backup available.