Long startup time after power supply is changed

I have a deskop PC here running Ubuntu 14.04 and observer very long start up time - about 5 minutes.

If the Ubuntu is already started and I restarted it, it takes about 30 seconds to load. So the issue is connected only with OS start after the PC is shut down.

What is going on:

1. First, detecting the IDE devices is too slow (about 15 seconds)
2. Then, the Ubuntu background is shown for a few seconds.
3. After that a black screen is shown for 3-4 minutes.
4. Then the login interface is displayed

As I have known, this started when the PC power supply was changed. I have no idea if the man who changed it changed the BIOS settings, too.

Could anyone help me idendity if this is a BIOS settings issue, new hardware issue or OS issue?