Tried 5 videos the first time I launched the YouTube app, and each time it said it couldn't display the video. Came back half an hour later, and all of those same 5 videos work. Videos had various durations.
Wifi enabled and connected both times, mobile network enabled both times as well, same background apps (gmail, handcent, etc.) running both times.
Here's something interesting I noticed though: In previous threads, people mentioned that if the YouTube quality was low, you could hit the [menu] while viewing a video and change the video quality to "high". In my YouTube app, though, when I was able to view the videos and therefore access that menu, the videos were already in high quality (I had an option to change to "normal" quality instead.)
Could it be that after the update the videos default to high quality, but you don't always have enough bandwidth to watch them that way? And if you can't start watching the video, then you can't change the quality setting.
--David