Yes, it can be an OS X version issue, that's what happens to my Mac Pro for the very same reason. If I try to start up the Mac Pro from a OS X 10.5 DVD, I got a kernel panic. Every time.
10.5 as 10.5.0, not even 10.5.2 right?, then it is the NVIDIA 8800GT, it is the same GPU I have here, my Mac Pro is the first revision so it would be able to boot with a 10.5.0 disc without any hassle if the Graphics Card inside it was the NVIDIA 7300GT, but since I had upgraded it to the NVIDIA 8800GT, I would need a 10.5.2 installation disc.
Yours being a newer Mac Pro would need to boot up from a OS X 10.5.1 disc minimum (if configured as it came from factory), but given you have the NVIDIA 8800GT you would need 10.5.2 or newer, cause that was the first OS X version to support the NVIDIA 8800 GT card.
All in all, I wouldn't be worried… try to get a 10.5.2 or newer OS X retail installation disc so you can confirm that is the issue here.
