O Redis está localizado no repositório Universe
De link
Universo - Software mantido pela comunidade, ou seja, não oficialmente software suportado.
Olhando para packages.ubuntu.com, a versão do redis-server nos repositórios 13.04 é 2.6.0, o que é bastante atual, embora possa usar uma pequena atualização para o 2.6.7. Como o Universe é suportado pela comunidade, talvez você queira enviar um bug contra o pacote aqui
Em link
lucid (misc): Persistent key-value database with network interface [universe]
2:1.2.0-1: amd64 i386
oneiric (misc): Persistent key-value database with network interface [universe]
2:2.2.11-3: amd64 i386
precise (misc): Persistent key-value database with network interface [universe]
2:2.2.12-1build1: amd64 i386
quantal (misc): Persistent key-value database with network interface [universe]
2:2.4.15-1: amd64 i386
raring (misc): Persistent key-value database with network interface [universe]
2:2.6.0-1: amd64 i386