AirPort Utility (5.6) stuck on "Configuring your existing wireless network to allow it to be joined"
AirPort Utility 5.6 isn't really supported anymore, so I found the only true solution to be to use Airport Utility 6.1.

To solve this question, I had to reset every single AirPort Express, Extreme and Time Capsule, but it works a lot better now.