Do you mean that safe mode doesn't make a difference - or that you can't boot into safe mode at all?
Your posts all lead into the likelihood that your hard drive is failing, or failed already. As safe mode uses the same boot partition, then you can probably expect that safe mode won't work either.
The hardware test does not do any extensive test of the hard drive, and really will pass the drive, as long as the drive responds as a storage device (but doesn't test to see if it is actually bootable) Your Disk Utility is a good test for that, and the fact that you can't boot to the drive is really the best test.
Did you find your original installer DVD?
Have you tried booting to Internet Recovery? Again, restart, holding Option-Command-R. If successful, you should see a spinning world (not the Apple icon). That will let you run Disk Utility to test the hard drive directory, and you can also download and install OS X. The internet recovery will upgrade you to Lion.