Are you using an external SD card, configured as internal rather than portable storage?
And is it configured as internal rather than portable storage? If so, try reformatting it as portable storage.
Try a clean reinstall following the steps in this post, including deleting the listed folders and rebooting your phone. Let me know if that works for you.
Thanks for the update. Yeah, cache cleaners and battery saving apps are pretty pointless on modern phones and can cause all sorts of issues.