This post recommends reducing your view distance as a solution to the problem:
http://www.wow.com/2010/06/24/patch-...storage-error/
For the record, I am experiencing this problem as well and that did fix it for me. I have also noticed that this patch has markedly reduced my frame rate... reducing the shadow detail greatly helps that issue.
So, there are definitely some serious issues in the graphics engine.