I'm having the same issue.
I have a 4-year-old iBook G4 Power PC (running 10.4.11) and an Airport Express purchased at the same time using WPA2 with DSL and a Westell modem. DHCP is enabled. I've never had a problem until now and this problem did not seem to correspond with any software patches.
When the Mac is awakened from sleep it can see the network and joins automatically, but cannot get anywhere on the Internet. If you try to go to Google Firefox just says "Looking up www.google.com..." and never connects...eventually getting a network timeout message. Same results with Safari and Opera. During this time my old WinXP desktop can connect and browse the Internet fine, ditto the Ubuntu Hardy laptop and brand new 32GB iPod Touch.
Running Network Diagnostics yields nice green lights on Built-in Ethernet, Network Settings, and ISP, but gives me ugly red lights on Internet and Server.
Interestingly, if I'm online with the Ubuntu laptop when the Mac is awakened from sleep it causes Internet connectivity problems for the Ubuntu laptop as well as the Mac's usual issue.
Workarounds have been spotty but the best results are achieved by unplugging the power cord on the Westell modem, then plugging it back in. Other tactics that occasionally work, but with no predictable consistency, are opening Mail and after it fails to connect, right-clicking on the error icon and saying "Go Online". I've even gotten it to work by opening iTunes and connecting to the iTunes Store, although this is unusual.
Any hints as to what's going on here?