Replacing a PSU is around a ten minute task with the only hard part being to make enough room to slide out the old unit and the new one back in again, but the more I read this one the more I have the feeling that something is holding the boot process up, as the P4 display item is comming direct from the bios. but too have power too the fans and then a delayed boot with normal operation from that point, I doubt the PSU is toast
Few quick check things you can try without a lot of dismantling, first off unplug the CD/DVD drive, both power and ribbon cables, and try again.
Then checking still with the CD/DVD drive disconnected to see if the HDD is spinning up correctly.
If this provides no solution try unplugging the unit from the mains and popping out the Bios battery for ten minutes to allow the board to discharge and reset the CMOS to default, pop the battery back in again and try a boot once more, if it boots correctly with no further problems I would guess something has altered in CMOS, possibly in the power saving area, if it boots once OK followed by faulty boots, I would be looking for a replacement Mainboard as this one is probably going home.