I found a solution, but honestly it's not entirely likely to be the problem anyone else is experiencing. Unless, of course, you're in an organization where the vast majority of your iOS devices are exhibiting this behavior, then keep reading.
It was not specific to the YouTube app, at least on my iPhone 5. If I went to youtube.com in Safari and tried to watch a video, it did not seem to start. The YouTube app failed pretty quickly with "Playback Error" usually, but I've also seen it fail to start playing, with the little waiting circle thingie spinning for what appears to be forever.
YouTube in Safari on my MacBook Air laptop, however, worked fine, and it was using the same Apple Airport Express Wi-Fi access points as the iPhones.
And, to complicate things further, all of the devices worked properly at Mom and Dad's. They use an Apple Airport Express access point and an Apple Airport Extreme that is a Wi-Fi access point, as well as being the firewall, router and DNS.
I tried several of the most popular and what to watch videos listed in the app, and all of them experience this problem. Note that many of these have a pre-roll advertisement, which may or may not be significant. While searching for advice on this problem, this was mentioned in a few postings.
Of course everything has been rebooted at least once. All software was updated to the latest version as of August 31, 2013. iOS 6.1.4, YouTube 188.8.131.5204. AirPort 7.6.4.
My great breakthrough occurred when I finally got a good packet capture of what's going on when a playback error occurs. 192.168.2.200 is my iPhone 5 and I started the capture just before playing one of the recommended videos for the first time, and a playback error occurred almost immediately. Here's a picture of the trace in Wireshark.
If you click on the picture it will open in a larger window which is presumably easier to read.
Anyway, what you can see is that the problem appears to be DNS related, which makes some sense. The iPhone is rejecting some of the DNS responses from my router. YouTube/iOS sends out an unusually large number of concurrent DNS queries, 9, in fact, 4 of which are duplicates. Several of these fail to resolve because iOS stops listening on the receiving port, which causes an ICMP destination unreachable message to be sent back to the DNS server (192.168.2.1).
In my case, I have a Netgear FVS-124 dual WAN router that acts as my border router and firewall. It also served as my DNS server. I've had mysterious hard-to-reproduce problems using this as a DNS server in the past, and, well, for whatever reason, it apparently decided to cause problems again.
I ended up installing a new recursive DNS server inside my firewall on a Linux server and pointed all of the access points to use that as the DNS for DHCP.
Important tip: Even though I changed the DNS sever IP address on the access points, iOS did not recognize the change. It continued to point at the old router-based DNS until I forgot the Wi-Fi network and logged back into it again.
And, wonder of wonders, everything then worked perfectly! Every video played exactly as expected on every device.
Since I really only worked around the problem, I don't exactly know the root cause. But I'll put some blame on YouTube for needing to query so many different host names to play a video, the iOS resolver for not coalescing queries for the same host in rapid succession before a response comes back into one request and some to the Netgear router, which is obviously doing something differently than Linux to confuse iOS, which may or may not be the fault of iOS.
In any case, if a large number of iOS devices in your organization are experiencing "Playback Error" in YouTube, stick a packet analyzer between the devices and your local DNS and see if you're getting a similar packet trace. If so, you're experiencing something similar to what I was seeing and you should look toward something DNS related.