To free up space on the root file system you can try to execute apt-get clean.
If that doesn't work you can go to /var/cache/apt/archives and manually remove a few files from the cache to get some space back, e.g.:
sudo rm linux-headers-*
It won't hurt to remove all of the .deb files here if you need to--that is what apt-get clean does. They will be automatically be re-downloaded by apt if they are again needed.
Freeing Up Space on the /boot File System
The Original Poster has a separate /boot partition, and that is what is full and preventing the apt system from working. It will be necessary for him to free up space there.
If there almost enough space, go to /boot and remove a config file or two:
sudo rm config-3.2.0-19-generic-pae
for example, but using the name of one of the kernel versions you intend to remove anyway. This will free up a little space (about 144K apiece).
If you need more space individually remove old vmlinuz initrd, abi and System.map files until you have enough space (about 22 megs for one of my i386 kernel versions).
Whatever you do, don't remove them all. You should at least keep the latest two matching versions of each kind of file, for each kind of kernel you use.
Then proceed with your apt-get install commands. As mentioned above they may have to re-download some of the debs you deleted, but if so that will happen automatically. When you have apt working again, clean up by using apt-get to remove the packages corresponding to the files you removed--so everything matches.
The config file in /boot is the kernel config that was used by the kernel team to build the kernel of the same name. It should be harmless to remove unless you want it for reference or to aid you in building your own kernels.
Finally you are manually removing an old kernel package or two from the /boot partition to make even more room for the new one.
