Alfred doesn't use your shell environment, which is what you see when you run locale or echo $LANG in Terminal.
The workflow takes its default locale from your system settings with defaults read -g AppleLanguages (it grabs the first result).
On my system, which has the preferred language set to "British English", I get:
(
"en-GB",
de,
en,
fr,
"zh-Hans",
"zh-Hant",
ja,
es,
…
…
…
)
Either change your Preferred languages in System Preferences under Language & Region so that "British English" is at the top, or append lang=en_GB to each of your formats, e.g:
dateadd %x lang=en_GB
will give you 19/06/2014.
The Region you have set in Language & Region is ignored, as a lot of users have it set to where they live but have their system set to use English/British English. This results in unusable locales like en_DE or de_IT.