Fontes obsoletas que foram adicionadas manualmente, também precisam ser removidas manualmente. No Centro de Software eu fiz o seguinte para remover a fonte:
Opened Ubuntu Software Center From the top menu selected Edit/Software Sources From the Other Software tab, unchecked the 2 entries for packages.medibuntu.org Selected both entries again/Remove
Agora posso atualizar sem problemas.