This is a strange thread for me, as I just solved the problem, but it took me ages and lots of frustration so I thought of posting just for posterity in case someone else has a similar issue. I was trying to add an Airport Express to my WDS network (to extend it to a nearby house - in my same compound). No matter which way I reset it (soft, hard, factory) the Airport Utility on my (wired in) Mac Pro never saw it (although it did detect my other working Airport Express that basically outputs iTunes to my living room). I reset both and did apple+r (rescan) in the utility ad naseum until I remembered how I solved this issue a couple years ago: a Mac that's actually on WiFi! So I hoped over to a MacBook I had close by and Airport Utility on that machine saw the factory-reset Airport Express and I got it configured and passworded up and running in 3-4 minutes. No idea why my Mac Pro, connected a gigabit speed to the same Airport Extreme base station can't see new Airport Devices (only fully configured ones, like the living room AE) but yeah, that's how I solved this problem.