Thanks for the tips
I've tried pretty much everything you suggested - reinstalled cpu, tried different ram and drives, removed drives, removed/disabled/unplugged almost everything, cleared cmos.. Last thing I'll try is a different graphics card.
Maybe it really is that slow. If someone is using the same board, please post how long does this step last for your board.