Sorry it took so long to get back to you Russell. No, you should not have to re-instal OS9. Since CS is already on your system, it "should" boot up and run it's own updates for any changes that occurred when you upgraded your OS. The one big complaint about OSX was that it (on purpose) was not backwards compatible to previous OSs, so programs that ran natively in OS9 will either a: not run at all or b: run much slower because OSX will first need to (either) boot a small version of OS9 (called Classic) or run a hidden emulator (which you will only notice because it takes a while for the program to boot). Confusing, I know.
The short version is, CS "should" run. If it doesn't, there isn't much you can do about it, unfortunately. The backwards compatiblity thing hurt a lot of people in the pocketbook for having to shell out for new software. You may have to purchase a new version of CS (if you know a student or an educator, you can get an educational version of CS4 Masterclass without the docs for around $500.00 through their university bookstore if that bookstore sells mac software).
I hope this helps.