It's also possible that the Ubuntu installation modified the partition table. I've seen this at a customer, where a Linux upgrade on a dual-boot system killed the Windows/WDE partition.
PGP WDE takes many steps to protect the MBR and partition table while in Windows. Unfortunately, those drivers/protections aren't loaded in Linux so it can modify the disk at will.
The customer referenced above was able to boot from the Recovery CD though and manually decrypt the Windows partition. He then used GetDataBack (see http://runtime.org) to fix the partition and recover his data.
I really don't know why the Recovery CD isn't working for you though. Is it possible that you're using a different Recovery CD version than the version of PGP WDE you had installed? Sometimes this occurs when the CD is cut on initial install, but not re-created after a WDE upgrade. Would it be possible to use a WinPE or BartPE disk instead? You'd need a separate Windows system to build the disk of course, but it might allow you to decrypt using the pgpwde command line. See KB article 807 for details -- I think you need a valid support contract to read the article though, since you can download PE tools and extra docs.
Finally, when you install WDE it takes the original boot loader and moves it into an encrypted area then installs Bootguard. After authenticating with the PGP passphrase, BootGuard chains to (executes) the old boot loader. This is the design, it works well in dual boot with non-Windows OSes, and sounds like is what worked for you initially. Unfortunately, it then sounds like the Ubuntu upgrade overwrote BootGuard with its own boot loader, eliminating your ability to auth to the Windows partition. We don't have a Linux product that could re-create the BootGuard code. However, Recovery CD or WinPE should do it -- though, as mentioned above, you may need to decrypt the disk first.
I know none of that solves your problem, but hopefully gives you some extra info and avenues to try.
