Ahah it seems that we ran into the same issues.
- Add the depot that contains the last versions
sudo add-apt-repository ppa:redislabs/redis
sudo apt-get update
- Install the new Redis version
sudo apt-get install redis
- restart redis
sudo service redis-server restart