Well, you are not alone, Windows people.
I have upgraded to iTunes 9.0.3 for Mac and my OSX is updated to 10.5.8, and I am having the EXACT same error...
"disc burner or software not found"
Before upgrading, although it has been a few months since I did it, I was able to burn CDs.
No help from Apple even for the Mac version. Go figure.