For those who are interested or who might have this same problem, I have a solution.

As I mentioned, I had both units set to run over 802.11G only, and this seems to be the root of the problem. I know the wireless router is working OK over G as I set my laptop up with a wireless card and it works fine. Just to try it, I set the router up to be in mixed mode and the print server up to work in mixed mode, figuring that it would drop to best connection, but this still didn't work. I then set the print server to try to connect over 802.11B only and this solved the problem immediately.
- it connected immediately using WPA-PSK
- it now happily reconnects after a power-cycle
- I went away on business and left it powered off for a couple of days, and it reconnected fine this morning when powered up.

So that seems to be the solution - thanks for those who replied to this, and I hope this solution can help others who are having this problem

Cheers

Robosmurf