Comment 2 for bug 1331298

Can you still reproduce the issue? Did you have some kernels installed that had greater version than the one that linux-image-generic depends on?

Please attach the output of
dpkg -l 'linux*' | grep ^ii
after this happens.

Maybe you had set package linux-generic as automatically installed?
Check that by
apt-mark showmanual linux-generic
If it prints the package name, linux-generic is manually installed, thus protecting linux-headers-generic and linux-image-generic from being automatically removed.