I'm thinking the problem is with the video card. I remember someone had a similar problem were Safe mode would work, but a regular boot wouldn't. It seems in Safe mode, aspects of the video card, aren't loaded and the problem wouldn't occur. Even the AHT would pass.
It would explain the Kernel Panic, why the Leopard Graphics update made it worse and of course the original problem to begin with.
Also, both OS's are having problems, which would seem to rule out any software conflicts. There is also a mention in the log about
"GFX0: family specific matching fails", and "NVChannel(GL): Graphics channel exception! status = 0xffff info32 = 0xd = GR: SW Notify Error" Which seems to me, to indicate the video card.
I hate to say it, but it might be time to have it looked at.