UTAU help for a non-newb noob.

First of all, I like 7-zip since it hasn't given me mojibake problems yet.

Secondly, you prolly need to redownload and unzip the VBs AFTER you change your locale. Redownloading the program doesn't change the VBs.

Another needed point is to have Japanese characters compability installed from your Windows disk (well, at least for WindowsXP, I don't know the others).
To be sure if you have the compability, try to rename any file with Japanese characters (while in Japanese locale or not. That shouldn't matter, I think). For example, create a .txt and close notepad, then rename it to "あ.txt" with the windows renaming interface. If it appears as mojibake means you haven't the compability installed.

But don't I think that's the issue (you can change to Japanese locale after all) so the tips from Aster should be enough. I do the same and it works.
I'm not sure you need to redownload the VB if you haven't edited them while in not Japanese locale, but you need to use 7-zip in Japanese locale for sure.