Zkušenost a touto chybou mám. Zakaž repozitáře backports, nepodporované, ppa repozitáře (zejména Gimpu, unity, gnome shellu, cinnamonu, ale raději všechny ppa).
Pak zkus ještě jednou sudo aptitude update; sudo aptitude install gimp. Nebo místo aptitude přes ten synaptic, ale obnov seznam balíčků. Pokud se nepodaří, tak přes aptitude vybírat tak dlouho jiné reseni, až tě to pustí.
Možná bude potřeba downgrade některých balíčků, některé přeinstalovat, možná i celé GUI.