I know similar issues have been resolved, but I'm kind of stuck. I ran out of space on / partition and needed to remove some packages since apt-get remove, autoremove and clean were not able to do anything. I then apt-get update and apt-get upgrade-ed, but something went wrong in the process. Now, the situtation is:

apt-get -f install

Reading package lists... Done

Building dependency tree       

Reading state information... Done

Correcting dependencies... Done

The following extra packages will be installed:

  linux-headers-server linux-server

The following packages will be upgraded:

  linux-headers-server linux-server

2 upgraded, 0 newly installed, 0 to remove and 56 not upgraded.

2 not fully installed or removed.

Need to get 0 B/3,996 B of archives.

After this operation, 0 B of additional disk space will be used.

Do you want to continue [Y/n]? Y

dpkg: dependency problems prevent configuration of linux-headers-server:

 linux-headers-server depends on linux-headers-3.2.0-55-generic; however:

  Package linux-headers-3.2.0-55-generic is not installed.

dpkg: error processing linux-headers-server (--configure):

 dependency problems - leaving unconfigured

No apport report written because MaxReports is reached already

                                                              dpkg: dependency problems prevent configuration of linux-server:

 linux-server depends on linux-image-server (= 3.2.0.55.65); however:

  Version of linux-image-server on system is 3.2.0.56.66.

 linux-server depends on linux-headers-server (= 3.2.0.55.65); however:

  Package linux-headers-server is not configured yet.

dpkg: error processing linux-server (--configure):

 dependency problems - leaving unconfigured

No apport report written because MaxReports is reached already

                                                              Errors were encountered while processing:

 linux-headers-server

 linux-server

E: Sub-process /usr/bin/dpkg returned an error code (1)

So the system wants to install linux-image-server=3.2.0.56.66 though other components depend on version 3.2.0.55.65. I tried to dpgk --remove the package and then reinstall, but I'm stuck. From what I understand, I would need to downgrade linux-image-server, then fix dependencies, than optionally upgrade, if it is needed?