結論
config/master.key をデプロイする必要がある*1。
解決方法（の一つ）
set :linked_files, 'config/master.key' という行をデプロイ設定のファイルに追加して、master.key ファイルを shared/config/master.key の場所に置けばよいです。
備考
環境変数 ENV["RAILS_MASTER_KEY"] で master.key の内容を指定してもよいです*2。
なお、database.yml や 外部API のトークン なんかも全部 credentials.yml.enc に詰め込めば、.gitignore するファイルは master.key だけになるので見通しが良くなると思います。ただ、それがベターな方法かと問われると現状ではちと分からないです。
