Redisの同時接続数制限が原因です。

Sidekiqのconcurrencyのデフォルトは25となっており、Redisにもその数だけ接続するため、デフォルトのままだと一気に25接続を消費します。Heroku RedisのHobby Dev(接続数制限20)のような低価格なプランでは、concurrencyの設定をせずにデプロイすると一瞬でログがエラーまみれになってしまうので注意しましょう……。

上記Wikiにもあるように、変更するにはsidekiq.ymlに以下のように書きます。RAILS_ENVごとに切り替えることもできます。

:concurrency: 5
staging:
  :concurrency: 10
production:
  :concurrency: 20