I have the same problem with my phone. It starts to play some video and it's completely frozen but it has audio, and after a while it gives that message. I have a Motorola Droid with no addons or anything special and it's not rooted. It's running the latest version of Android. I can't play videos on Youtube or any videos I've taken on my phone. Please help this is extremely annoying. Thanks in advance!