I was having a very similar problem. My update manager would always report "Not all updates could be installed". Whenever I tried this:
sudo apt-get update && sudo apt-get upgrade
I got this:
The following packages have been kept back:
0ad 0ad-data ginn libgrip0 linux-generic linux-headers-generic linux-image-generic touchegg
Then I did:
sudo apt-get purge touchegg 0ad 0ad-data
Because I knew I didn't need those anyway.
After that the command line was still giving me the same as above. Then, for no particular reason, I did System Settings > Details and clicked the Install updates button. For my surprise it installed all those packages without any issues..
Very weird.. hope this helps.