Well, I got the problem directly after an update of the 2.6.31-11 kernel (it was already installed). I don;t know if this is related. As I have two partitions (system and home), I expect two messages of fsck. However, it only showed clean for system and then it did nothing - no message about my home partition, and no possibility of booting. Every time I booted with 2.6.31-11, the boot stopped after one message of fsck. I succeeded in booting with the 2.6.31 kernel (I got that from the mainline kernel ppa. 2.6.31-10 is based on 2.6.31, 2.6.31-11 is based on 18.104.22.168), and after that I was able to boot again with the 2.6.31-11 kernel (which showed now two times clean).
I don't know if the fsck check was the problem, and if that was the case, I don't know if there was a forced check planned; when I succeeded in booting with the other kernel, I had to check both hard disks because of another bug on the LiveCD which sets the super block time wrongly. fsck detects this and forces a check because of this error, so I don't now if a check was scheduled before.
However, it is really possible that it is related: I only booted once with the other kernel and did not install any updates. The only thing that changed was that I had one successful boot in which I had to (manually) check both partitions.