AirPort Express OK as client with WEP not WPA

Working configuration:
-Existing non-Apple network setup with 128-bit WEP
-AirPort Express in client mode
-PC with Linksys router WKPC54G with latest firmware 1.55.02
-Laptop with Linksys notebook adapter WPC54G

My issue:
In my current setup with WEP, I am able to setup my AirPort Express as
a client connected to my existing home network. I can see it from the
admin utility, play through iTunes AirTunes, on both my PC and laptop.
This is good. However, if I switch my network and all relevant devices
to WPA, I can only see the base station and play music from the PC.
The problem is with accessing the AirPort Express from the laptop
after switching to WPA. After switching to WPA, the laptop can see the
router (I can ping it and receive replies), but cannot see AirPort
Express (I get no response from a ping). I know I've correctly setup
WPA because I can access other computers on the network from my laptop
through the router.

My guess is that the PC->Router->AirPort works because WPA is not
involved. However, when trying Laptop->Router->AirPort fails because
WPA comes into play. Any thoughts?