Are you sure that this video is still uploaded on Google Video?
Oh, I feel like an idiot. :-[
Even though I had triple checked the id of the video I still managed to enter the incorrect code... I had an extra number at the end of the code which was causing the issue.
Everything is working fine now. Thank you Katia for your advice!