OK, lately I've been having two problems with my computer:

1. It crashes often. This in and of itself is a minor nuisance at worst; however,

2. Whenever it shuts down for any reason, it stays down. This problem started a few months after I got this computer; it would take a few restarts sometimes, maybe 5 minutes. By the summer it was taking 15 to 20, ocassionally longer, but for most of the semester it's been loading quite smoothly... up until a couple weeks ago. Now it's taking as long as an hour and a half from when I shut it down until when it will boot back up, and it's happening more consistently than ever before. During this time, if I just push the on button, my computer tower will light up and make a few noises, but my monitor, speakers, etc. will give no indications of being connected to a running PC; moreover, after waking up my hard drive just sits there humming softly, making none of the heavier noises associated with the actual startup procedure. Then, having waited about an hour and a half, I press the button again, and poof! It starts up normally.

Anyone have any ideas what the problem could be?
The first thing that comes to mind is that your BIOS is fried, but then it should not start at all if that is the case (but ya never know).

It is possible that the BIOS needs to be upgraded to fix any problems associated with the motherboards it is installed on. I'd check the BIOS manufactuers website to see if there are any flash-rom updates you could perform. Be careful about the instruction, and backup everything before attempting the update.

This definitely sounds hardware related... another thought was about CPU temperature monitors - some are made to prevent the computer from damaging itself if the CPU is too hot, or a fan is not working properly, by not allowing the machine to boot. But I would think you would get a warning notice during startup about that...

Have you added any hardware (a graphic card, or more memory for example) just prior to these problems?
I had the same problems a while ago. Then it just poof! up and went away.
Im having no problems with restarting anymore. I cant think of anything I did to solve it.
I was having a similar problem not too long ago... deducing that the problem was hardware based, I found the perfect hardware-oriented solution: I bought a new computer.
I had this exact same problem. It was still under warrenty, and the shop ended up replacing the mother board twice, the power supply twice, and the CPU once. Then I bought a very expensive UPS just to make sure I wasn't frying things with bad AC. Things stabilized for awhile, but eventually I was having weird crashes.

I wiped the HD, and attempted to re-install Windows, and FAILED. I tried Windows 2000 and XP, both from original CDs, and they would not install. I was ready to buy a new computer.

Then my buddy at work told me it sounded like a problem with my memory. I took out the chips I had put in, and installed without a hitch. I since swapped out the chips to find the bad one, and left it out of the equation. Everything has been smooth as silk ever since.