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