bitcoind: corrupted database? looris@Palace-of-the-Nine-Moons:/tmp $ bitcoind 
looris@Palace-of-the-Nine-Moons:/tmp $ Bitcoin server starting


************************
EXCEPTION: St13runtime_error       
CLevelDB(): error opening database environment Corruption: missing start of fragmented record(2)       
bitcoin in AppInit()       


This happens when I start bitcoind, any clue on what could I do to fix it?

I tried to run it with -rescan but the result was the same.
Just run ./bitcoind -reindex and this will fix your problem.

-rescan is for missing wallet transactions