Depois de estar no seu mesmo barco, e não encontrando ótimas respostas, acho que descobri por que você (e eu) estávamos tendo problemas: Freya está apenas em Trusty. Isso significa que se você estiver executando uma versão acima do que está listado, o ppa apontará para um repositório não existente por padrão.
Então, executando isso:
sudo add-apt-repository ppa:elementary-os/stable
Será assim, uma vez instalado:
link
Que atualmente não existe.
Estou assumindo que, no momento em que você tentou isso, o Trusty ainda não era considerado estável.
Portanto, para evitar isso, adicione a versão desejada. Eu não sou o suficiente de um cão BASH para saber como fazer isso a partir do terminal. O comando listado na barra de ativação do eOS não parece funcionar para mim.
MAS, você pode realizar a mesma coisa no Synaptic. Vá para os repositórios clicando em Configurações > Repositórios e vá para o repositório do Elementary OS e clique em "editar". Em versão, mude para Trusty em vez de sua versão.
Devo mencionar que isso pode ser o motivo pelo qual as pessoas estão recomendando usar o diário em vez do estável. O eOS parece um pouco atrás da distro principal dos lançamentos (compreensível), então só porque você está no mais recente Ubuntu estável não significa que seja o último eOS estável.
Espero que ajude.