I am also facing the same issue and got the same error message. I did a lot of things to sort this issue out but I still can't do upgrade. I did:
- I logged out and login to single user mode (init 3)
- apt-get update && apt-get upgrade
- aptitude safe-upgrade
- removed vlc and did sudo apt-get update && apt-get upgrade && apt-get dist-upgrade
Any help is greatly appreciated ..
Ps: Upgrade broke my system when I did the force upgrade, I reinstalled it