Não tenho certeza se devo postar isso como resposta ou editar no post original, mas aqui está: Eu tinha motivos para acreditar que o Cinnamon estava, pelo menos parcialmente, causando todos os conflitos e outras coisas (coisas em geral não pareciam como eles deveriam) então eu removi todos os pacotes associados com o Synaptic, além de todos os outros pacotes de terceiros e tentei atualizar através do Update Manager e ele realmente funcionou! Problema resolvido, mas obrigado pela dicas caras!