Eu tive o mesmo problema. Eu não quero parecer bobo, mas eu achei que era a minha conexão de rede. Eu estou em um escritório onde temos segurança de internet apertada na LAN com fio. Eu tenho trabalhado nisso por 3 dias agora. Assim que mudei para a nossa rede pública sem fio, consegui executar a limpeza e atualizar sem problemas. Espero que seja assim tão fácil para você.
FWIW: Estou rodando o Zorin Linux com kernel 3.5.0-23 em 64bits