Shall I give up? I have the exact same problem. My MacBook connects to my 2wire wireless router no problem. If I connect the AE directly up to my laptop via Ethernet, I can see it... but if I want to see it consistently it is only after a hard factory reset.
Anyways, once I've done this and try to configure it to connect to my 2wire network, it simply doesn't work. The SSID is hidden on that network but like I said my MacBook can connect to it just fine through WPA Personal, if I specify the SSID name. The Airport Express OTOH says it can't find it, despite the fact it's only 3 feet away.
Why is Airport Utility such a POS? I had similar problems with my graphite Airport 802.11b way back when, which is why up to now I never bought another Airport base station. I had hoped that Airport Utility all these years later would be better, but nope.