Tive um problema parecido com o Kubuntu Natty, e foi resolvido trocando de servidor, do servidor do Brasil, para servidor principal, vá nas configurações pela central de programas e na aba outros softwares troque de servidor, acho que resolve. Até logo :-D