Cela me rassure car je n'ai donc pas désinstallé cinnamon (même pas à l'insu de mon plein gré) mais c'est une mauvaise mise à jour de libmuffin0 qui a mis le désordre.

Ensuite apt-get install libmuffin0 a donné ceci :
Les paquets suivants contiennent des dépendances non satisfaites :
libmuffin0 : Dépend: muffin-common (= 1.0.6-20120817024007-precise) mais 1.0.6-20120819024005-precise devra être installé
E: Impossible de corriger les problèmes, des paquets défectueux sont en mode « garder en l'état ».

Amusant les dépendances... un paquet peut en cacher un autre voire plus...

Ensuite apt-get install muffin-common a donné ceci :
Lecture des listes de paquets... Fait
Construction de l'arbre des dépendances       
Lecture des informations d'état... Fait
muffin-common est déjà la plus récente version disponible.
muffin-common passé en « installé manuellement ».
0 mis à jour, 0 nouvellement installés, 0 à enlever et 0 non mis à jour.

Ce qui semble bon.
Mais non ! :-)
Lassé j'ai fait
apt-get update
apt-get install cinnamon
Je vous passe le détail des réponses.... :-)

et là çà semblait être bien bien (pour résumer)
Pour vérifier çà je vais relancer... et donc terminer ce message...
Je vous tiens au courant de ce passionnant feuilleton !

apt-cache policy cinnamon

te dira s'il est là ou pas

sudo apt-get install cinnamon 

S'il installe Cinnamon c'est que tu l'as désinstallé par inadvertance sinon il te dira que le paquet est déjà installé et là il faudra chercher quel est le souci.