Es ist schwierig nachzuvollziehen, was Du selbst schon ausprobiert hast. Hast Du denn mal
.... die Spiegelserver gewechselt?
.... geschaut, was passiert, wenn Du diese Pakete im Terminal mit APT neu installierst ?
.... Synaptic selbst neu installiert ?