Today I downloaded the installer for OSX Lion from the App Store. I ran it, and when it came to choose the disk to install to, it told me that "this disk cannot be used to start up your computer". I had a setup with 4 partitions: the hidden EFI system partition, the Macintosh HD partition, and two linux partitions (an ext3 one + a swap one).
So, the solution was to resize the Macintosh HD partition. I booted my Mac from the Lion install DVD (you can burn it from the installer package, just search google to know how to do it), went into disk utility, checked all partitions for errors (this was necessary because I wasn't able to resize them otherwise) then I resized only the Macintosh HD partition shrinking it by some GBs.
After this, I ran the installer again and installation started smoothly.