The fact that it would not go into the bios routine sounds like a CPU problem, not a hard drive issue. Have you checked the cpu fan? If it's full of cat hair, it may be allowing the cpu to overheat. It may be at the point where it jams, stops a while, then unjams and runs a while. This would produce exactly the effects you are describing... random program lock-ups, unreliable boots, long boot times, etc.

Be sure to remove the screws holding the fan onto the heat sink and blow all of the dust out of the fins on the sink. When I was doing computer repair for a couple of years I fond that this was a quick fix to about 2/3 of the random issues customers would describe along these lines.

Hope this helps.