A few days ago I started to get the error “Insufficient storage available” when updating Apps on my Samsung S4 – running Cyanogenmod 11. I Googled it – and was recommended me to install various “cleaning” Apps – and also make sure I wasn’t out of storage space – which I wasn’t.
What actually fixed the problem was to open File Manager (which comes with Cyanogenmod) – and deleting folders inside /data/app-lib/ for the Apps that refused to be updated. Often the Apps had several folders – indicating that an Update had beenattempted – but failed. Delete all folders related to the App.
The folder names might not correspond 100% with the name of the App. If you are unable to find the folder for an App – then simply go to Settings > Apps > XXXXX and look at the namespace (marked in red below). The folder will have this name as well.