私の場合、redisinitを次のように変更することでこれを解決しました:
REDIS = Redis.new(:url => redis_url_string)
以前はURIを解析し、引数を次のように渡していました:
uri = URI.parse(redis_url)
REDIS = Redis.new(:host => uri.host, :port => uri.port, :password => uri.password, :scheme => uri.scheme)
キャッシュストアのinitには、redis用の同様のinit実装があるのだろうか(ソースを確認していません)。