O software no Ubuntu é instalado a partir de repositórios de pacotes contendo vários pacotes. Isso é diferente dos instaladores "clique em próximo" no Windows.
Então, você removeu o Multiwinia, mas os repositórios permanecem lá.
Mas ter os repositórios geralmente não é um problema, o erro ocorre devido a problemas de conexão ou repositório da Internet instáveis.
Para remover o repositório, abra o Ubuntu Software Center > Editar menu > Fontes de software > clique na guia "Outro software" > Desmarque os repositórios indesejados com 'multiwinia'.
OR
Abra um terminal > tipo:
sudo gedit /etc/apt/sources.list
Remova estas linhas: [cuidado com este arquivo!]
link
link
Espero que isso resolva seu problema.
Edit: Existem mais arquivos de lista de repositórios na pasta /etc/apt/sources.list.d.
Por exemplo, as reposituras do Google Chrome estão em /etc/apt/sources.list.d/google-chrome.list
Então, você pode procurar em /etc/apt/sources.list.d por arquivos como multiwinia.list e remover o arquivo. Faça um backup antes de excluir ou editar qualquer coisa, a menos que você esteja absolutamente certo do que está fazendo.