A questão é que você está seguindo as instruções erradas. A página que você vinculou fornece as seguintes instruções para o Ubuntu 13.10 (64 bits):
$ wget -c https://launchpad.net/~stebbins/+archive/handbrake-releases/+files/handbrake-gtk_0.9.9ppa1~raring1_amd64.deb
$ sudo dpkg -i handbrake-gtk_0.9.9ppa1~raring1_amd64.deb
$ sudo apt-get install -f
Os que você seguiu, usando o PPA, são para versões mais antigas do Ubuntu. Presumivelmente, o PPA que você está tentando usar não tem uma seção para 13.10, portanto, quando você tenta executar apt-get install handbrake
, nenhum pacote é encontrado.