Is it an asus motherboard? I think that bios might be a possible culprit too, since reverting to an older version did reduce boot time.My Linux Mint has been taking a long time to boot lately too.
Now I have the same booting problem that you do so I know how you feel.