Does this happen with all videos? That should only happen if the video is either, well, private (but in that case you wouldn't even be able to see it listed) or because the owner has not enabled the video for mobile viewing.
Have you tried switching to WiFi and see if it plays? I had an issue where YouTube wouldn't play over 4G, but as soon as I moved to 3G or WiFi, it would be fine (it turns out my carrier has a problem with Facebook and YouTube over 4G right now...)