I had similar issues twice. Once it was because I'd accidently made a backup in cwm to the internal storage. Android just reported me as only having 2gb of storage rather than 4. Like the phone just came with that. Cleaners didn't work but going into that recovery and deleting the backup did.
And...a few times after installing a ROM I'd have no free space, nothing would install, and deleting things would cause less, not more free space to be reported. Never figured that one out except to wipe and reflash and it would go away.