Abschließend lässt sich leider gar nicht mehr genau feststellen, was zu dem Problem führte was mich jedoch lange beschäftigte. Durch ein Update des Linuxkernels bzw. der Kernelheader trat ein dependency Problem auf, welches sich nicht durch apt-get -f install / autoremove /clean oder ähnliches beheben ließ. Bei jeder Paketinstallation und jedem Upgrade brach der Updateprozess mit dem folgenden Fehler ab:
Die folgenden Pakete haben unerfüllte Abhängigkeiten: linux-generic-pae : 
Hängt ab von: linux-image-generic-pae (= 3.2.0.37.44) soll aber nicht installiert werden
Hängt ab von: linux-headers-generic-pae (= 3.2.0.37.44) aber 3.2.0.38.46 soll installiert werden
linux-image-server : Hängt ab von: linux-image-generic-pae soll aber nicht installiert werden
Die Lösung fand ich dann nach einger Recherche hier: http://askubuntu.com/questions/251862/broken-count-error-linux-generic-pae-depends-linux-image-generic-pae-3-2 Das linux-generic-pae Paket muss zuerst mittels dpkg entfernt werden und kann dann mit apt wieder mit den korrigierten Anhängigkeiten reinstalliert werden.
sudo dpkg --remove linux-generic-pae
sudo apt-get install linux-generic-pae