Demaestro - 4:10 pm on Apr 7, 2010 (gmt 0)
Youtube has been rolling out massive layout and playback changes. I haven't seen what you are describing but I have been encountering other errors in the past week.
I would just give then at least another week to get everything all figured out.
I would remind your boss that you get what you pay for, and if the videos having a 99% up-time is a requirement then he should move to a paid service that would guarantee such a thing.
If free is what he wants them I would go with something like what Stout suggested.
Have the video embedded from Youtube and a link to a 2nd source like Vimeo in case Youtube is down.
Do let your boss know that the outage more than likely had to do with massive updates being rolled out on Youtube for the past week.