I have that exact Powerbook, and I noticed a big speed bump after upping the RAM to 768MB and adding a 7200rpm HD in there. I know there's some place that'll let you send them your Powerbook and they'll put in a new logic board with a 1.2Ghz G4 on it, but I think it's between $400 - $500, which makes it too much to be worth it, in my book.
I'd say try the RAM and HD upgrade, and if you still feel it's too slow, just get a new Powerbook. Oh, and put the 7200rpm drive in the new one, too.