Same here. My issue is wifi only. iPhone 4 latest update, 4S latest update, and iPad 2 latest update. iPhones play videos fine on 3g and 4g. Just started out of the blue on May 2.
My PC and Mac computers all play YouTube videos fine over my wifi. Still I updated router firmware, reset cable modem, cleared caches history and cookies, reset iOS devices, cleared network settings, restart, reboot, etc. to no avail.
YouTube app fails, m.youtube on safari fails, sometimes I get "request timed out" or "video currently unavailable" or "network error."
Anyone else with this problem have more to add? I suspect it is YouTube failing somehow, and not my devices or network. Perhaps defaulting to flash versions of videos for some reason? Thinking out loud...