Comment 2 for bug 1515316

I just had a problem that looked similar to yours, i.e. seeing: KeyError: "The cache has no package named 'linux-generic-lts-utopic'

I had upgraded from 14.04 to 15.04, and then wanted to go to 15.10. It seems that certain xserver/nvidia packages had been kept at trusty. I removed them, and then it prompted to install the vivid versions (although they were older). Unfortunately that led to a situation where I couldn't boot X as the kernel headers were not installed.

Anyway, everything now working, perhaps, at 15.04. But upgrade still fails. Stuck at calculating changes. My apt.log file is attached.