I have this same problem with no solution with two devices so far that i switched out for.
I used eugene's vibrant rom as the rom and ryanza's lagfix. Is there anyway that it is the rom's problem or the phone problem?
A couple of people who experience the same problems with so far no solutions:
dogizmo . com /gadget/getting-storage-memory-error-message
forums . t-mobile . com /t5/Samsung-Vibrant/Vibrant-memory-storage/m-p/450474