Not sure if it has to do anything with this, but when I was experiencing slow starts and hungs for a long time I used
checkblocks=50
in my bitcoin.conf
This tells the client to only check the last 50 blocks and speed up everything. 50 should also be safe even with the latest blockchain split issue, based on the recommended 30 blocks confirmation waiting time.
I got the error still with that added to bitcoin.conf, though it might have loaded quicker.