Lembra como você configurou a sua rede na primeira vez? O App achou seu Airport mesmo sem estar configurado. De alguma forma, a Apple criou uma maneira dos Airports conversarem com o Utilitário independentemente da rede. Não sei explicar como isso funciona, mas funciona.
Na minha rede, o rei dos problemas é o Time Capsule que gerencia a rede. Na primeira vez, fiz de tudo, como você, depois, no desespero, mandei esquecer a estação, já disposto a fazer um hard reset e começar tudo do zero. No meu caso significava configurar 6 Airports, mas a coisa simplesmente voltou a funcionar.
Como você já está com problemas na rede, o que tem a perder?