I've been using Redis Lab for a while now, but I want to switch to something cheaper and more easily scalable.
RedisToGo, RedisGreen, RedisCloud, and openredis are all viable alternatives. You can also run your own redis in AWS if you like.
I've used RedisToGo via Heroku and never had any issues with them but can't speak to the scaling challenges you may face when using them.