Just to add to the many good messages in this thread - I had reason to update the locales on Ubuntu 18 for a server in Singapore. Three languages are running in Moodle - English (GB), Tagalog and Filipino (both get installed if you choose one of those in Moodle). The Language Customisation page was telling me that the required info was not on the server and Moodle was defaulting to AU...
To fix:
1 - log into your server with the command line, and depending on your flavour of Linux, and your permission levels (you may not need the 'sudo' bit), run:
sudo dpkg-reconfigure locales
2 - A pink screen will open asking you to select the locales that you want. Scroll through using the arrow keys, and select using the space bar all that you need... or select 'ALL' at the top of the list.
3 - hit the return key and follow the prompts (it'll ask you which you want as your default) until you are back at the command line. The system will tell you it is generating the locales:
4 - type: sudo apache2ctl restart
(again, depending on your level of privilege - you may not need to type 'sudo'... but I do)
The system will restart apache and in doing that will restart PHP too. If you then refresh the page in your Moodle you should see the error message about languages has gone.
Took me a moment or two to remember to use the 'Space' bar for making the selection on the pink page... not enough caffeine, clearly.