How Do I Fix: "Safe mode: Warning: Displayed transactions may not be correct!"
Typically, this is caused by a corrupted block chain database - it causes your client to consider the real chain invalid, and try to find another one. Since the real chain remains the longest obviously, it shows this warning, as it notices its opinion differs from the rest of the network.

The solution is deleting blkindex.dat/blk000?.dat and let redownload the chain. In case you're running 0.8 (if not, upgrade), you can just use -reindex to rebuild the database (no downloading necessary in that case).