I have just gotten this error "Uncompressing Linux.. invalid compressed format (err=2) System halted_" on a machine that has been running "Breezy" just fine for quite awhile. It has been rebooted several times since the latest updates with no problem.
I took this to the Ubuntu forums but they have been less than helpul so I came back home with it. I guess it's possible that there is an issue with the kernel, but like I said it was rebooted several times after the last update with no problems. Could also be some bad sectors on the drive I suppose. I have Suse on this drive also and it runs fine.