My wife's iPad is giving her a "storage almost full" error several times a day now, but under Usage it says she has 4.4 GB available, and in iCloud she has 16 GB available so where is the storage almost full?
That is weird- she may have some files lingering after OTA updates. I assume you have tried rebooting the device? I would also clear out the Cache in safari- See if any of those things help.