500 error on some users with MFA enabled

Some of our users on our GitLab CE (Omnibus) installation can’t log in to GitLab. We force MFA and after they have provided username and password they are flashed with the 500-error page instead of the expected MFA input page.
The same 500-error page is shown if we try to Impersonate the user as a GitLab admin.

Eventually these logs can help:

==> /var/log/gitlab/gitlab-rails/production.log <==
Started GET "/profile/two_factor_auth" for 10.0.2.207 at 2017-02-27 16:26:03 +0000
Processing by Profiles::TwoFactorAuthsController#show as HTML
Completed 500 Internal Server Error in 14ms (ActiveRecord: 1.2ms)

OpenSSL::Cipher::CipherError (bad decrypt):
 app/controllers/profiles/two_factor_auths_controller.rb:5:in `show'
 lib/gitlab/middleware/multipart.rb:93:in `call'
 lib/gitlab/request_profiler/middleware.rb:15:in `call'
 lib/gitlab/middleware/go.rb:16:in `call'