OK, thanks for the additional.
I remember there being an issue with 10.4.x not connecting via WPA reliably, but WEP working normally. WPA support was introduced in one of the 10.4.x Tiger updates. I believe if you can get it upgraded to 10.5.x Leopard it will support WPA easier.
Also, you could try downloading and installing the
Mac OS X 10.4.11 Combo Update (PPC) over the top of your current install, in case part of the networking software didn't get updated properly or is corrupted somehow.
You can't upgrade the Apple AirPort card, as there was only one that was compatible. USB Wi-Fi devices are sometimes a bit flakey, especially those that are old enough to still support the PowerBook G4 and PPC.
C