For anyone who is interested, I have now solved this problem:
I was running 98Lite, which is windows 98 with IE removed. The palm desktop software require IE 5.0, (although I don't think the support documentation mentions this, it wasn't on the "system requirements" when I bought the Palm). After installing "regular" windows, I could install the software no problem.
So, if in doubt, don't try and and install palm software on a custom windows installation, stick with windows fresh out of the box, security holes and performance hassles and all.