Scusa una domanda stupida, dato che presumo tu abbia già provato ; ma hai provato a cancellare la cache in base all'output?
Se non l'avessi fatto e volessi tentare l'ultima spiaggia prima di procedere alla reinstallazione, taggami e fammi sapere che vedo di darti qualche info in più.
In pratica, è una situazione a grandi lineee che ci si può ritrovare quando la cache di "apt" è troppo incasinata, ed ignora i repository (a volte gran colpa l'hanno i ppa: )per un "path" che tende a non riconoscere...