grrrrrrrrrrrrrrrrrr , it bothers me when i see it !
well not any more , i have recently been getting alot of [We're sorry, this video is no longer available.] from youtube , so i googled here & there and found out that the main reason for this is google web accelrator .
By disabling / uninstalling it it will solve your problem , however , it wasnt my case , i never had it installed , so i figured out it might be some other plugins and this time it was AVG safe browsing that comes with AVG 8 free edition .
if you are still having troubles with youtube , try disabling one or more of 3rd party’s plugins 
if the problem persist , refresh/reload the page
Easy fix, for all windows vers. In internet explorer go into Tools/Internet Options/Connections Tab/Lan Setting. Once in Lan Settings, uncheck all boxes. ALL youtube videos will load now.
Pass it on.