I was going to spin a long-winded tale, but I'll just get to the point...

My deuced Mac(hina) was having problems connecting to my AirPort Express Base Station after restarting, and, ultimately, AirPlay stopped working and AirPort Utility was unable to deal with either of my two Base Stations (for different reasons, no less), although I still had wi-fi internet.

A fortuitous shut down/start up cured all ills.

Good old, basic troubleshooting still works!

A router/Airport shutdown and restart are often as beneficial as a computer restart.

I had already toggled AirPort off/on, unplugged (the only way to "turn off"), even hard-reset (which didn't take ), my Base Station, and restarted my deuced Mac(hina), but with no joy.

So, at that point I booted into Apple Hardware Test, and after short test came back negative I started an extended test, decided that it was pointless, and shut down with the power button rather than wait for it to stop on its own, and it was only when I started up again that things righted themselves.

It was definitely the shut-down that turned the trick.

Edit: I forgot to mention that I was experiencing wildly different issues with two different Base stations.

A truism so old that it is often overlooked or forgotten is a reboot (a.k.a. warm boot) is NOT the same as a shut down and boot (a.k.a. cold boot). There are a few registers in the CPU and other parts of the system that are not reset in a warm boot and only a cold boot will clear those registers. In rare cases a problem can only be solved by clearing those registers. The old "rule of thumb" was,

Also as any call to AppleCare will likely remind you, a warm boot does an abbreviated hardware POST test. Among other things, it skips the short memory test.