You can test to see if it's a problem with Chromium's built-in Flash player by joining YouTube's HTML5 trial, which will switch you over to YouTube's new HTML5 video player. If the videos work then, something is messed up with your installation of Chromium/Flash player. Try reinstalling it. If they still don't work, it may be a problem on YouTube's end or your ISP's end or somewhere in between. Could you comment with an example of a video that's giving you this error?

Also, does this appear to be a YouTube error, or an error that you're receiving from Flash/Chromium?