"-15000" errors, including "-15006" are firewall-related. Here are the steps that an AppleCare engineer took me through, to resolve my issue (see above). I reached this engineer only after two escalations, so this is not a well-known issue or fix.
(These instructions are for a Netgear router - non Netgear devices should have very similar options and nomenclature)
0) Quit iTunes
1) Open your Web browser and in the URL field, enter "192.168.0.1" (typically the default URL for your primary router, regardless of make).
2) This should bring you to the Admin screen of your main home router (for example, Netgear - not the Airport Express itself). If you secured your router, it will prompt you for your ID and password. If you don't remember it, you may need to do a "factory reset" and then re-set it up with a new name and password, then re-setup the security, such as WPA2 (remember to write it all down!!!)
3) In the admin menu, select the menu option that lets you specify Ports and port exceptions. In the Netgear admin menu, this is under "Advanced/Port Forwarding & Port Triggering," for example.
4) You will now add a "rule" that allows iTunes to stream over your router. Select "Port Triggering" and "Add service." You will be prompted to name this rule - I used "iTunes streaming." Then, "Service type" is TCP, the triggering port is 548.
5) Under "required inbound connection," enter Port 548 (which is TCP / Apple Filing Protocol over TCP) through Port 554 (TCP/UDP / RTSP for streaming media players and Quicktime Streaming Server). If there is an option for it, make sure that "Service user" is set to "Any" so everyone using your network can get to it.
6) Save settings, exit your router's Admin screen, using the "exit" option in your router's admin screen. Don't just close the window.
7) Restart iTunes. You should see a dropdown menu in the lower right hand corner of the iTunes window, labeled "Computer." When you click on it, the resulting dropdown menu should also list your AirPort Express routers.
Additional troubleshooting:
If you have the firewall enabled on your Mac itself, go to System Preferences/Security/Firewall/Advanced and remove iTunes from the list (select it, press the "minus" symbol at the bottom of the list window), then hit the "plus" symbol to re-add it.
Both the "Stealth Mode" and "Automatically allow Signed Software to receive Incoming Connections" options can be enabled - should make no difference.
If this still doesn't work, you may need to re-setup the AirPort Express routers themselves. Use the AirPort Utility to do this. Join existing network (you may need to enter its name, security type and password manually. Remember to name your router with a name that you will remember later.
This fixed mine!