You've a lot unused kernels. Remove all but the last kernels with:

sudo apt-get purge linux-image-{3.0.0-12,2.6.3{1-21,2-25,8-{1[012],8}}}

This is shorthand for:

sudo apt-get purge linux-image-3.0.0-12 linux-image-2.6.31-21 linux-image-2.6.32-25 linux-image-2.6.38-10 linux-image-2.6.38-11 linux-image-2.6.38-12 linux-image-2.6.38-8

Removing the linux-image-x.x.x-x package will also remove linux-image-x.x.x-x-generic.

The headers are installed into /usr/src and are used when building out-tree kernel modules (like the proprietary nvidia driver and virtualbox). Most users should remove these header packages if the matching kernel package (linux-image-*) is not installed.

To list all installed kernels, run:

dpkg -l linux-image-\* | grep ^ii

One command to show all kernels and headers that can be removed, excluding the current running kernel:

kernelver=$(uname -r | sed -r 's/-[a-z]+//')
dpkg -l linux-{image,headers}-"[0-9]*" | awk '/ii/{print $2}' | grep -ve $kernelver

It selects all packages named starting with linux-headers-<some number> or linux-image-<some number>, prints the package names for installed packages and then excludes the current loaded/running kernel (not necessarily the latest kernel!). This fits in the recommendation of testing a newer kernel before removing older, known-to-work kernels.

So, after upgrading kernels and rebooting to test it, you can remove all other kernels with:

sudo apt-get purge $(dpkg -l linux-{image,headers}-"[0-9]*" | awk '/ii/{print $2}' | grep -ve "$(uname -r | sed -r 's/-[a-z]+//')")

Your boot partition is full. Since this is a kernel update, these files will be copied to the boot partition so you need to clean in out. Here is a blog post that will show you how to clear the old kernel images with one command. I'll give a basic synopsis of the method. Use this command to print out the current version of your kernel:

uname -r

Then use this command to print out all the kernels you have installed that aren't your newest kernel:

dpkg -l linux-{image,headers}-"[0-9]*" | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e '[0-9]'

Make sure your current kernel isn't on that list. Notice how this is the majority of the final command (down below). To uninstall and delete these old kernels you will want to pipe these arguments to:

sudo apt-get -y purge

Now we can do everything we want by combining these last two commands into this unholy mess:

dpkg -l linux-{image,headers}-"[0-9]*" | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e '[0-9]' | xargs sudo apt-get -y purge

And that one command will take care of everything for you. I will confirm that this does work perfectly but never trust anybody on the internet. :) For more info, the blog post gives a very good explanation of what each part of the command does so read through it so you are satisfied that it does what you want it to do.

sudo apt-get autoremove

This command is doing the job automatically.

The Synaptic Package Manager can be used to easily select and remove old kernel images.

If you don't already have Synaptic installed:

sudo apt-get install synaptic

Start the application and select the options shown.

You should be able to highlight all the "linux-" packages with the version "2.6.x" where x is between 31 to 38 according to the files in your /boot folder.

Right-click each of those linux packages and choose the option "Mark for Complete Removal". Finally click the apply button. This will remove all the files and any associated files. Your /boot folder should now be a bit tidier.

Thank you for your detailed post of your problem, this got me going in the right direction. Although it is useful to keep previous kernel files you can remove all of them in one go, check this post:
How to Remove All Unused Linux Kernel Headers, Images and Modules

Done via command line. If you are doing this via remote use something like WINSCP to open a terminal session and just paste it in, works very well.

Here it is copied from article link, I suggest you read the full article:

dpkg -l 'linux-*' | sed '/^ii/!d;/'"$(uname -r | sed "s/\(.*\)-\([^0-9]\+\)/\1/")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*/\1/;/[0-9]/!d' | xargs sudo apt-get -y purge

This is a new answer to an old question, but an easy way to clean this thing (and more) is to install Ubuntu Tweak. To install it:

sudo add-apt-repository ppa:tualatrix/ppa
sudo apt-get update
sudo apt-get install ubuntu-tweak

then you can run Ubuntu Tweak, Going to the "janitor" tab, and from here it's a matter of three clicks:

It is better to leave the last kernel (you never know) or a well-known working kernel for safety, though; but that's easily customizable.

You can use the same tool to clean a lot of things --- just remember that if you clean thumbnail cache or TB cache then the system will have to rebuild them if they are needed.

I was able to fix the problem by using dpkg to remove the packages directly. Although the packages are still listed in dpkg -l, the files are removed from /boot, freeing up space.

phrogz@planar:/boot$ sudo dpkg --remove linux-image-2.6.32-30-server
(Reading database ... 145199 files and directories currently installed.)
Removing linux-image-2.6.32-30-server ...
Running postrm hook script /usr/sbin/update-grub.
Generating grub.cfg ...
Found linux image: /boot/vmlinuz-2.6.32-35-server
Found linux image: /boot/vmlinuz-2.6.32-34-server
Found initrd image: /boot/initrd.img-2.6.32-34-server
Found linux image: /boot/vmlinuz-2.6.32-33-server
Found initrd image: /boot/initrd.img-2.6.32-33-server
Found linux image: /boot/vmlinuz-2.6.32-32-server
Found initrd image: /boot/initrd.img-2.6.32-32-server
Found linux image: /boot/vmlinuz-2.6.32-31-server
Found initrd image: /boot/initrd.img-2.6.32-31-server
Found memtest86+ image: /memtest86+.bin
done

# Repeat for kernels -31 and -32 and -33, up to (but not including)
# the version listed by `uname -a`

After this, apt-get -f install fixed my dependency problems, and all was well with the world.

I'll not be accepting this answer of mine, however, as I still need to know if I should be increasing my /boot size or doing something else.

You can stop using a separate /boot partition, then you won't have such limited space there. To do this, unmount the partition, then mount it somewhere else and copy all of the files there to the /boot directory in your root partition, then remove the entry from /etc/fstab and reinstall grub. For example ( you will need to use the correct partition ):

sudo -s
umount /boot
mount /dev/sda2 /mnt
cp -a /mnt/* /boot/
umount /mnt
gedit /etc/fstab
grub-install /dev/sda

You can then use gparted to delete the old /boot partition, and possibly extend the root partition to use that space. To extend the root partition you will need to boot from the livecd, and the free space needs to be immediately to the right. If the /boot partition is currently to the left of the root partition, then you will need to first move the root partition to the left, then extend it, but this can take a very, very long time, so may not be worth the trouble.

List all kernels:

dpkg --list 'linux-image*'

Display current kernel:

uname -r

List all kernels EXCEPT current one:

dpkg -l linux-{image,headers}-"[0-9]*" | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e '[0-9]'

Make sure your current kernel isn't on that list.

Remove all kernels EXCEPT current one:

dpkg -l linux-{image,headers}-"[0-9]*" | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e '[0-9]' | xargs sudo apt-get -y purge

Clear other stuff:

sudo apt-get autoremove

If it still gives you boot disk space error for installing/uninstalling files then directly remove one of OLD image from /boot directory,

ls -lh /boot/*-3.13.0-119*;

rm /boot/*-3.13.0-119*; 

NOTE: Please review current kernel image again before deleting any image.

If it stills throws any error then repeat following commands to remove unwanted kernels,

sudo dpkg --purge linux-image-X.X.X-XXX-generic linux-image-extra-X.X.X-XXX-generic linux-signed-image-X.X.X-XXX-generic
sudo dpkg --purge linux-image-Y.Y.Y-YYY-generic linux-image-extra-Y.Y.Y-YYY-generic linux-signed-image-Y.Y.Y-YYY-generic

sudo apt-get -f install

dpkg -l linux-{image,headers}-"[0-9]*" | awk '/^ii/{ print $2}' | grep -v -e `uname -r | cut -f1,2 -d"-"` | grep -e '[0-9]' | xargs sudo apt-get -y purge

Taking the best from the answers above, my tried-and-true approach is this:

• uname -a to find the running kernel.
• dpkg -l linux-{headers,image}-\* | grep ^ii to list all currently installed kernel-related packages. This will include the running kernel.
• sudo apt-get purge linux-{image,headers}-3.16.0-{xx,yy,zz} to remove the old kernels. Replace xx,yy,zz with a list of the kernel builds you want to remove—these are all the builds listed by the previous command which are older than the currently running kernel. Make sure you don't remove the currently running kernel—your system will become unbootable. You may also need to change the kernel version from 3.16.0 to whatever is installed on your system.
• Optionally, do an additional sudo apt-get autoremove—this will remove any leftover dependencies of the old kernels which are no longer needed by the current one, freeing up some more space.

You may have header files without matching kernel versions installed, or vice versa—just include all of these versions in the command. APT will complain that some packages can't be removed because they are not installed, but that will do no harm.

If something fails...

• If the apt command fails due to a no space left on device error, use the corresponding dpkg command instead: sudo dpkg --purge linux-{image,headers}-3.16.0-{xx,yy,zz}.
• If the dpkg command still doesn’t work because the linux-image packages are required by the linux-headers packages of the same version (which you also want to uninstall), dpkg may have failed to resolve that. Re-examine the output of dpkg -l and specify any package name suffixes on the command line. For example, on one of my systems the command that eventually worked was sudo dpkg --purge linux-{image,headers}-3.16.0-{xx,yy,zz}-generic-pae.
• If you get any other error, seek help—you may have a different problem than you thought.