Can't update apps (Error downloading App/Insufficient storage)

I can no longer update any apps on my device (Ainol-Novo 7 Fire running 4.0.4), I'm getting two errors, either "Error downloading "App", or "Insufficient storage available".
I have installed App Cache Cleaner, I have cleared the Download Manager cache and data, I have deleted Google Play Services which got it working long enough to update two apps, but then the problem returned. Now no solution will work and I'm unable to update anything.
The problem was intermittent until recently and usually using App Cache Cleaner to clear the cache solved the problem, but not anymore.