I recently fresh installed Linux Mint 12 (Lisa), which is based on Ubuntu 11.10 (Oneiric). I almost immediately bumped into a problem with gdebi, the graphical package installer. The message I received was:
"Could not open XXXX.deb. The package might be corrupted or you are not allowed to open the file. Check the permissions of the file."
After a lot of searching, I found this solution in linuxmint forums. Works like a charm:
[code]sudo apt-get install xz-lzma[/code]