Acredito que a solução mais fácil no momento seria a formatação mesmo. Se você não tiver arquivos importantes para fazer o backup, seria o que eu recomendaria.
É preciso tomar muito cuidado ao manipular pacotes entre esses sistemas. O Debian fornece a base utilizada no Ubuntu, mas os sistemas em si são diferentes. Até mesmo entre versões do próprio Debian você poderia encontrar erros: DontBreakDebian - Debian Wiki
Usar pacotes do Ubuntu no Debian (e vice-versa) é algo que sempre devemos evitar, exceto quando realmente indispensável. E deve ser feito com cautela.