I found that the only thing that worked for me was using Aptitude.
sudo aptitude
Then when it opens it will usually say something about unmet dependencies on the bottom. You can hit the letter g to proceed with the suggested removal. It will take you to a page where it lists what is going to happen.
There should be a minus - next to the broken kernels. Press g again and it will remove the broken kernels. Press q to quit. Then you should be able to use sudo apt-get autoremove to get rid of the old kernels and free up space.