Linux tends to be highly tolerant of faulty hardware, but it is entirely possible that the hardware is failing.
Facing the same systems, I probably would have made the same assumption.
I use Ubuntu Linux myself and it never complains about the 500 GB DVR hard drive in my computer while the Windows XP I dual boot with always complains about it.
I never tried to find a program on Ubuntu that would do a defrag or a surface scan or anything like that on the HD, but you might want to look into it. There should be something similar invented by somebody already.
As for the computer booting up slowly, my Ubuntu boots up more and more slowly every time I upgrade to a newer version (Jumpy, Lucid, Natty, etc). I think this is pretty normal for Ubuntu and it might be a good idea to make an all new CD and blow away all of Ubuntu and completely reinstall with a CD of the new version from scratch every 3 or 4 versions because of it.
That could have something to do with that problem.