I unexpectedly fixed the problem.
A few weeks ago, after trying everything, I gave up and decided go backwards by reinstalling Tiger. Once I did that, things started running well once again. I got the latest patches on Tiger and reinstalled the programs.
Even though it was shutting down properly once again, I stilled yearned for the Leopard.
Then I decided to give it one last try.
Before, everytime I did a "clean" installation of leopard (including the very first time I installed it), I always chose to do format my drive completely when installing leopard because I liked the feeling of being "fresh". I would back up all my files on an external hard drive. I had not actually done a "regular" upgrade. For some reason, everytime I chose to format it completely, the shutdown problem was always there.
This time, I did a regular upgrade, I have had no problems at all.
Now, every since I reinstalled Tiger, updated and installed all programs and patches, then installed Leopard (and choosing update, NOT archive or format) then it has been working properly.
So basicly, Do a completely SWEEP by installing TIGER, Upgrading all patches and installing all your programs, then do a simple installing UPGRADE with Leopard (not archive or format).
That is what worked for me. If you have tried everything and have nothing to lose, then maybe this might work for you. I hope this works