sudo apt-get update && sudo apt-get upgrade
Resolveu no meu Ubuntu-14.04 e no Xubuntu-14.04
O problema desse comando é que irá atualizar tudo, tudo mesmo. Se tiver muita coisa que não usa e que não se preocupa em atualizar, daí vai demorar.
Por exemplo, nunca atualizo coisas do gimp, por exemplo, pois não uso.