"initdb: encoding mismatch" when running gitlab-ctl reconfigure

I am installing Gitlab-ce Omnibus in a Vagrant box (Debian 18.04 LTS). In my provisioning script, I run gitlab-ctl reconfigure. I get an error:

initdb: encoding mismatch

Console output:

default: * execute[/opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8] action run
default: 
default:     [execute] The files belonging to this database system will be owned by user "gitlab-psql".
default:               This user must also own the server process.
default:               
default:               The database cluster will be initialized with locale "en_US".
default:               initdb: encoding mismatch
default:               The encoding you selected (UTF8) and the encoding that the
default:               selected locale uses (LATIN1) do not match.  This would lead to
default:               misbehavior in various character string processing functions.
default:               Rerun initdb and either do not specify an encoding explicitly,
default:               or choose a matching combination.
default:     
default: 
default:     
default: ================================================================================
default:     
default: Error executing action `run` on resource 'execute[/opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8]'
default:     
default: ================================================================================
default:     
default: 
default: 
default:     
default: Mixlib::ShellOut::ShellCommandFailed
default:     
default: ------------------------------------
default:     
default: Expected process to exit with [0], but received '1'
default: 
default:     
default: ---- Begin output of /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 ----
default: 
default:     
default: STDOUT: The files belonging to this database system will be owned by user "gitlab-psql".
default: 
default:     
default: This user must also own the server process.
default:     
default:     The database cluster will be initialized with locale "en_US".
default:     STDERR: initdb: encoding mismatch
default:     The encoding you selected (UTF8) and the encoding that the
default:     selected locale uses (LATIN1) do not match.  This would lead to
default:     misbehavior in various character string processing functions.
default:     Rerun initdb and either do not specify an encoding explicitly,
default:     or choose a matching combination.
default:     ---- End output of /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 ----
default:     Ran /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 returned 1
default:     
default:     Resource Declaration:
default:     ---------------------
default:     # In /opt/gitlab/embedded/cookbooks/cache/cookbooks/postgresql/recipes/enable.rb
default:     
default:      80: execute "/opt/gitlab/embedded/bin/initdb -D #{postgresql_data_dir} -E UTF8" do
default:      81:   user postgresql_username
default:      82:   not_if { pg_helper.bootstrapped? }
default:      83: end
default:      84: 
default:     
default:     Compiled Resource:
default:     ------------------
default:     # Declared in /opt/gitlab/embedded/cookbooks/cache/cookbooks/postgresql/recipes/enable.rb:80:in `from_file'
default:     
default:     execute("/opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8") do
default:       action [:run]
default:       default_guard_interpreter :execute
default:       command "/opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8"
default:       backup 5
default:       returns 0
default:       user "gitlab-psql"
default:       declared_type :execute
default:       cookbook_name "postgresql"
default:       recipe_name "enable"
default:       domain nil
default:       not_if { #code block }
default:     end
default:     
default:     System Info:
default:     ------------
default:     chef_version=13.6.4
default:     platform=ubuntu
default:     platform_version=18.04
default:     ruby=ruby 2.3.7p456 (2018-03-28 revision 63024) [x86_64-linux]
default:     program_name=/opt/gitlab/embedded/bin/chef-client
default:     executable=/opt/gitlab/embedded/bin/chef-client
default:     
default: Recipe: gitlab::gitlab-rails
default:   
default: * execute[clear the gitlab-rails cache] action run
default: 
default:     - execute /opt/gitlab/bin/gitlab-rake cache:clear
default: 
default: 
default: Recipe: gitlab::redis
default:   * ruby_block[restart redis svlogd configuration] action create
default: 
default:     - execute the ruby block restart redis svlogd configuration
default:   * ruby_block[reload redis svlogd configuration] action create
default:     
default: - execute the ruby block reload redis svlogd configuration
default: 
default: 
default: 
default: Running handlers:
default: There was an error running gitlab-ctl reconfigure:
default: execute[/opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8] (postgresql::enable line 80) had an error: Mixlib::ShellOut::ShellCommandFailed: Expected process to exit with [0], but received '1'
default: ---- Begin output of /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 ----
default: STDOUT: The files belonging to this database system will be owned by user "gitlab-psql".
default: This user must also own the server process.
default: 
default: The database cluster will be initialized with locale "en_US".
default: STDERR: initdb: encoding mismatch
default: The encoding you selected (UTF8) and the encoding that the
default: selected locale uses (LATIN1) do not match.  This would lead to
default: misbehavior in various character string processing functions.
default: Rerun initdb and either do not specify an encoding explicitly,
default: or choose a matching combination.
default: ---- End output of /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 ----
default: Ran /opt/gitlab/embedded/bin/initdb -D /var/opt/gitlab/postgresql/data -E UTF8 returned 1
default: Running handlers complete
default: 
default: Chef Client failed. 141 resources updated in 01 minutes 00 seconds
The SSH command responded with a non-zero exit status. Vagrant
assumes that this means the command failed. The output for this command
should be in the log above. Please read the output to determine what
went wrong.

Already tried, didn't help:

cat > /etc/default/locale <<EOF
LC_ALL=en_US.UTF-8
LANG=en_US.UTF-8
LANGUAGE=en_US.UTF-8
EOF

localedef -v -c -i en_US -f UTF-8 en_US.UTF-8 || true