The problem is that X doesn't support ja_JP.utf8, only ja_JP.eucJP so that when X boots up, it can't find the charmap for japanese UTF8 and drops back to the default which is GB UTF8.
So this works:
echo -n "Which language?"
case $LANGUAGE in
ja) export LANG=ja_JP.eucJP
echo "Language set to Japanese"
en) export LANG=en_GB.UTF-8
export "Language set to English"
*) echo "Using default English"
I found this out by looking at the /etc/sysconfig/redhat-config-language/language.py script which shows the possible options and yep, ja utf8 is not one of them. My other proprietary OS uses UTF8 which supports half-width japanese characters - actually a much better charset to use but it's a cross we'll have to bear.
I can change the language at the login prompt again now.
Schroedingers cat is dead. I killed it.