Works fine for me. I would suggest to set YouTube to always use HTML5. If you still have issues, then please add the info you get when you click "Learn More" to your question. (Turns out there is no further useful information.)
Investigation and troubleshooting
I think I was able to reproduce this issue and up until now I didn't modify any settings in about:config as Zoltan mentions while HTML5 versions of YouTube and Vimeo have both been working fine for me. I just installed gstreamer1.0-libav
which got me this far on YouTube's HTML5 page:

Regarding your error message, as I said I never modified related settings in Firefox or installed any extensions or plug-ins that might change these on your behalf. You should check entries beginning with media.
in your about:config and reset them back to default via double click or context menu → reset. You can or should leave the media.gmp-
settings alone, then restart Firefox and HTML5 YouTube should be working as intended. The is as close to the default as possible with libav/ffmpeg providing the necessary codecs.
The issue seems to be triggered by an inconsistent configuration, which confuses YouTube, especially you when don't restart Firefox and Flash is also still in the mix (you should restrict usage of Flash and only enable it when necessary). Another trigger could be that H.264 and VPx content gets mixed one video would play, but the other has issues and cause the message you got. I imagine an ad loading before the actual video, the ad would not play, playback would not continue and throw the error message, while the actual video would have played just fine. N.B. I'm a NoScript user and notice that I don't see as much ad clips as I see without.
Reproducibly enable all HTML5 video features

With everything set to a default (reproducible) state you can try to enable all features on the HTML5 page. Here is how:
Install gstreamer1.0-libav
or the latest available version of the package if you haven't already. Then set the following settings to true in about:config (the current default in Firefox 41 is false):
media.mediasource.enabled;true
media.mediasource.webm.enabled;true
media.fragmented-mp4.exposed;true
media.fragmented-mp4.ffmpeg.enabled;true
The following are just to check, they should be enabled by default:
media.gstreamer.enabled;true
media.webm.enabled;true