Since I managed to solve the issue, I figured I'd tell you guys too :P
This is a copy of the message I sent there:
Well, I found out the cause of the problem: it seems that my previous
install of Ubuntu somehow managed to create a swap partition that
overlapped a bit of the beginning of the next partition. As a result
anything that used libparted could not read the partition list
properly, leading to that issue. I tested it with a livecd, using
gparted, and it showed the same result.
After running testdisk with a deep search, I removed the malformed
swap partition and created a new one, and succeeded in installing
lenny :)
Thanks for the help!