Of course, recommending they change browser is very different from displaying a "download the WebM codec
to view the video".
I can't tell if you're being sarcastic or not, since clearly changing browsers is a hugely larger action than installing a codec. I'll assume you're not, for the sake of conversation.
Are you trying to imply that installing a codec is more difficult than installing a browser? This is probably true by default, but we could easily create an executable giving you a simple click-to-install experience for the codec.
Plus, I've been suggesting this whole time a subtle-ish message off to the side, while the Flash video still plays, not a "This video is failing for reasons you can't possibly understand, click here for magic that will make it work again." message.