Just got my Airport Express today and I had the same error message. After trying several ideas, I finally got the AE to accept changes by plugging my laptop directly into my network. In other words, I plugged my ibook into my switch directly and then ran through the set up. After saving my configuration, I disconnected the ethernet cable and everything has been fine since. I don't know why I needed to be "wired" to do the initial config, but, hey, at least it worked.
Alfie
