I am getting the message box shown in the screenshot below when watching videos on YouTube using Firefox 4.0.1. Also, Adobe Flash is crashing very often. It's not only YouTube, I can see this message on almost all streaming videos. I am running Ubuntu 11.04 on a ThinkPad x300.
You can read all about Flash's Local Storage here.
To configure it, browse to these webpages (both lead to tabs in the Flash Player's settings manager):
Global storage settings
Settings for already visited sites
Note, that those settings are global and not bound to the browser. If you change anything with Firefox, the change will also affect Chromium, Opera, etc.