Unsupported locale prevents me from starting apps

Question

I have the following locale settings when I type export:

declare -x LANG="es_ES.ISO-8859-1"
declare -x LANGUAGE="es:en"
declare -x LC_ADDRESS="ms_MY.UTF-8"
declare -x LC_IDENTIFICATION="ms_MY.UTF-8"
declare -x LC_MEASUREMENT="ms_MY.UTF-8"
declare -x LC_MONETARY="ms_MY.UTF-8"
declare -x LC_NAME="ms_MY.UTF-8"
declare -x LC_NUMERIC="ms_MY.UTF-8"
declare -x LC_PAPER="ms_MY.UTF-8"
declare -x LC_TELEPHONE="ms_MY.UTF-8"
declare -x LC_TIME="ms_MY.UTF-8"

I am Spanish living in Malaysia, so I actually want my system in Spanish but with the country setup for Malaysia. I actually don't know whether I have set it up right or not.

Now, I try to launch a recently installed application, git-gui (amongst some others), and I just get the following error message:

$ git-gui
We are sorry, command-not-found failed! Please send a bug report at:
https://bugs.launchpad.net/command-not-found/+filebug
Please attach the following info to the report:

command-not-found version: 0.3
Python version: 3.3.1 final 0
Distributor ID: Ubuntu
Description:    Ubuntu 13.04
Release:        13.04
Codename:       raring
Exception information:

unsupported locale setting
Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/CommandNotFound/util.py", line 24, in crash_guard
    callback()
  File "/usr/lib/command-not-found", line 69, in main
    enable_i18n()
  File "/usr/lib/command-not-found", line 40, in enable_i18n
    locale.setlocale(locale.LC_ALL, '')
  File "/usr/lib/python3.3/locale.py", line 541, in setlocale
    return _setlocale(category, locale)
locale.Error: unsupported locale setting

So how can I fix my locales? What would be the right setup for my system to match my requirements and also the requirements of applications such as git-gui?