apt-get not working on Ubuntu 16.04, problems with kernel packages

Solution 1:

The problem is here.

cp: omitting directory '/etc/udev/rules.d/49-teensy.rules'

Remove that directory and re-run and everything should be fine.

For me this helped!
Just remove all the linux-image and image-extra files, which are problematic by running:

$sudo mv /var/lib/dpkg/info/<>packagename<>.* /tmp/
$sudo apt-get autoremove && sudo apt-get autoclean

Then update/install the latest one by running:

$sudo apt-get install linux-generic