I'll assume you're using the latest revision firmware in the WAP54G. Sounds like you did everything correctly.
A few things to try:
- Disable WEP and see if DHCP now works. It usually does.
- The algorithm for converting ASCII keys to hex seems to vary by manufactory. Try using a 10 digit hex 64bit key or a 26 digit hex
- Download the free "DHCP Query Tool" from: formatting link's at the bottom of the list. Load it on a malfunctional laptop and see what it does. You do not need to have an IP address for this to work as DHCP uses all 1's broadcast. I've seen where the DHCP server returns garbage and the client ignores the garbage as some type of sanity check. It might also be that the WAP54G is blocking broadcasts for some odd reason (it shouldn't).