I have a similar problem as you described, however I have troubleshooted the problem down to my PowerBook (12"/1.33Ghz). It seems that every time I sleep the PowerBook it will reconnect to the Extreme upon wake, but I can't use the Internet. I end up having to reset the Extreme or restart my PowerBook. It's very annoying. However, it does not happen with my iBook or PC notebook.
Do you have DSL or Cable Modem? The latest two Apple firmware updates for AirPort Extreme and Express are not compatible with certain modems that use PPoE to connect (most notably those from SBC). If you perform the firmware update to 5.7 (Extreme) and 6.3 (Express), make sure you have firmware 5.5.1 (Extreme) and 6.1.1 (Express) available in case your modem is not compatible.