Well indeed I just cleared the data from a number of apps: Living Social, Twitter, and a few others, and the low storage icon went away.
Must be related to Gingerbread because this just started since my update this week. And I have plenty, plenty of internal storage and memory. Must be a bug. And it's very annoying.