Thank you. I had the same problem, and following your advice, I've removed (as root) one of the applications that wasn't optified.

In my case, I've solved the problem removing youtube-dl. I couldn't use apt-get, because it had a failure, due to the lack of space. I just did:
# rm /usr/bin/youtube-dl
# touch youtube-dl
# dpkg --configure -a

And then I was inmediately able to run apt-get...