A temporary work-around I've found is to use the Airport Utility on my iPad.
I've been having the same issue, with both my MacBook Air and iMac. I have an Airport Extreme (4th gen.), with an Airport Express (1st gen.) connected to the network as a Airplay device only.
At first, I only updated the software on the iMac, then noticed that it would not connect, while the Air still would. Then, I clicked update on the Air without thinking about it, and now it doesn't work on either computer.
The Airport Utility on my iPad is now the only way to communicate with either device. Hope this helps you, and I really hope Apple fixes this soon for everyone.
I was having the same problem. I had installed a new router and was trying to reconfigure my Airport Express to connect to the new network. I kept getting the "unexprected error message" using Airport Utility 6.3.
But this article suggested a solution that worked : http://support.apple.com/kb/TS4597
Once I had changed my PIv6 settings, I was able to get into the Airport Express and change the network I wanted it to connected to.
I worked around the problem by using the old Airport Utility on my old Mac laptop, and directly connecting to the Time Capsule with an Ethernet cable. But I can't get the new Airport Utility 6.3 to recognize the 4th generation Time Capsule, running it from either my 2012 MacBook Air or my 2011 Mac Mini (both on 10.7.5). The light on the Time Capsule is green and the Network Diagnostics says "Your internet connection appears to be working correctly." I tried the "solution" in the article http://support.apple.com/kb/TS4597 on both newer systems, but it didn't work on either. Please, Apple, fix this soon.
I bought a 3TB time capsule yesterday and connected it to my network easily, and as everyone else has found, realized that having updated my Airport Utility to 6.3 on my Macbook Air and our iMac, all 6 of my Airport Express devices set up to drive speakers in various locales were now invisible. The purported IPV6 "fix" from Apple was, not suprisingly, useless. I did multiple hard resets on every one, and of course, despite all logic to the contrary, 2 of the 6 eventually were seen by APU on my Mac Air. Multiple restarts of the Time Capsule, all manner of other workaround including hooking eack APE unit to the computer with ethernet were unable to get them recognized.
I tried multiple times to download an older version of APU but the OS doesn't let you delete the new one and install the old one. I know if I was more tech savvy there is probably a workaround for this as I seem to have read but it's a bit beyond what I am capable of.
So, my ultimate solution...we had an old iMac from years ago mothballed in the basement that I could never bring myself to clean up/sterilize the HD and sell but that we never need/use. Hauled it up, unpaired the mouse from the iMac, paired it to the old machine and got it all running, and in minutes the old Airport Utility had every Airport Express listed in the sidebar ready for configuration with the new netork. Ten minutes later every one is up and running.
The only glitch is that on the APU v. 6.3 on my Air and iMac "sees" every Airport Express unit, correctly named for their locations in the house, etc., but there is no green light/dot next to the icon. If I wasn't listening to music through them I would assume they were offline or not connected but I can use iTunes and iPhone remote app like always. My conclusion, for now, is not to even mess with the current disaster that is APU 6.3 until they (Apple) acknowledge it's a complete failure, unless I want to cough up another 400$ for new Airport Express units.
So perhaps readers here can locate an older version of APU the way I did.
I'm having the same problem, however, thinking the problem was my old AP Extreme I ran out and bought the newest APE. I'm running OS 10.8.1 and APU 6.3. The AP extreme is seen in the wifi menu, but I cannot get into the new APE AT ALL to configure it. Also, I attempted to get through to the AP Exteme via my iPad running iOS 7 and get the same error message. Any suggestions?