Aparentemente está tudo em ordem com os repositórios.
Este mundão de ppa's podem estar fazendo esta confusão.
Veja se pelo synaptic voce consegue instalar => pidgin-libnotify
[]'s
Achei a dependência, mas ao tentar instalar o Synaptic acusa:
pidgin-libnotify:
Depende: pidgin mas não será instalado
Depende: pidgin mas não será instalado