The test you are performing on the hard drive is a Drive Self Test. That is the drive is checking itself.
So generally it cannot detect problems caused by a bad cable, wrong jumper settings, interface problems on the part of the drive, bus sharing problems (ie the drive is a poor master or slave).
Nor can it detect problems with the motherboard's IDE controller.
That being said it still tells you a lot about what isn't wrong which is very handy.
---
As far as memtest86 you just let it run all its tests for awhile. It will record any errors. You need to let it finish at least one complete pass. That is do each test at least once. Most people like to let it complete a couple passes just to be certain. People often find it convient to run overnight.
Of course other factor can cause memory errors, a flaky motherboard, bad powersupply ....
But if the memoy passes all tests without errors then you know it is in perfect working condition.
---
You may also want to check your IDE cable and power connections.
DATA and power cable's sometimes develop intermitent faults. By that I mean that most of the time they work, but if you bend or jar them you may momentarily lose connection in one of the wires.
That would definately cause problems like the ones you are experiencing.
---
PS the long startup is likely your OS performing tests because the file system was not shut down properly.
Some other tests to run
HD Tach to benchmark your hard drive. If the results are abnormally low or erratic this could indicate a problem.
Prime95 to test overall system stability. Ask in the overclockers forum how to run this and other stability test. Overclockers have to be expert stability testers.
---
There is of course the chance that it is a software problem. Backup your OS and try a clean install if nothing else works.