If you haven't tried, go to your Safari menu bar click Safari > Empty Cache. Try a video.
If that didn't help, back to the menu bar click Safari > Reset Safari. Select the top 5 boxes, click Reset. Try again.
If that didn't work either, quit Safari.
Go to ~/Libray/Caches/com.apple.Safari/Cache.db
To find the Home folder in OS X Lion, open the Finder, hold the Option key, and choose Go > Library
Move the Cache.db file to the Trash.