iPod Touch: Music Video Not Found?!

Okay: There's me, trying to watch Oren Lavie and Coldplay music videos on my iPod, sitting in a car for a long car ride. Suddenly, a little banner pops up the instant I click on the video and says "The requested video was not found on this URL." I tried watching my other music videos: Only one worked out of 4. Any ideas on how to get them back? Restarting didn't help.