On my AirPort Express:
If I had another Mac or Windows PC that was able to connect, I'd run the AirPort Utility on that machine to check the AirPort Express's settings.
If I didn't have a way to get back in, I'd hit the paperclip reset button briefly to do a "soft reset" -- this just makes the network visible and security-free for a short time, so you can get wirelessly associated again if you'd forgotten your network name or password.
I'd choose to manually set the channel, and pick one that seems clean (based on using a tool like iStumbler to see what networks I can see around me are on what channels). I'd probably pick a 2.4GHz channel (1-11 or 1-13) because I'd probably have some 2.4GHz-only devices around like iPhones.
I would double-check what wireless security type and password it was using, so that I can enter it correctly on my MacBook if need be.
I would disable the "Closed Network" (hidden network) feature of the base station, because it doesn't really offer much security, and just makes the network harder to get reconnected to when things go wrong.
I would disable any MAC-address based Access Control Lists (ACLs). I think they may call it "Timed Access" now. This doesn't offer much security either, and again mostly causes hassles.
I would make sure I have up to date firmware on the AirPort Express. There have been two versions of AirPort Express: the current one that can do 802.11n, for which the latest firmware is 7.5.2, and the older one that only does 802.11g and earlier, for which the latest firmware is 6.3.
If I were still running the older AirPort Express that can't do 802.11n, I'd go buy a new one. The older b/g model, which was introduced in 2004 is showing its age at this point. Connecting modern 802.11 clients to the older Express seems to cause it to become unstable.
On my MacBook:
I would run the Software Updates tool on my MacBook to make sure I have all the latest software updates on my MacBook as well.
I would go into "Utilities > Keychain Access" and search my keychains for any entries concerning the problem network, and delete them (they'll automatically get re-created later when I'm able to successfully join the network).
I would go into "System Preferences > Network > AirPort > Advanced > AirPort" and edit my Preferred Networks list, deleting any entries I don't honestly need anymore, and delete the entry for the problem network. (I'd let that entry get auto-recreated the next time I'm able to successfully join that network.)
I would go into "System Preferences > Network > AirPort > Advanced > TCP/IP" and make sure I had that set correctly (which probably means making sure it's set to get its address from DHCP).