Im assuming the client adapters you have are 802.11b. If you say you can connect fine when using an a/b/g card, the security setup sounds fine. On the AP web interface, select Network Interfaces, then select your 802.11G radio, and then the settings tab. Here you will likely see the speeds for the radio 1Mb/s 2Mb/s etc are set to require. If so, hange the throughput speeds to enable instead, and apply the changes. You should now be able to connect using an 802.11b card.
If that wasn't the problem, I'd check for firmware/driver updates for the card.
Damien.