Selected Answer
It seems like the only solution that has worked for other people is to copy the affected add-ins from a machine that has them in English. Apparently, Excel converts these to the last language that you installed, or something similar to that.
Here is what was mentioned:
copy in the Solver folder in C:\Program Files\\Microsoft Office\Office12\Library from a computer with it in English and it will then appear in English
And this seemed relevant too:
I also found that the solver add in the add-in list in excel options was also in Korean and a registry hack fixed it (again taken from a comp. with it in english)
Export the registry key:
HKEY_CLASSES_ROOT\Installer\Components\5B5EF7AEDE9827842B7BD01C302B3B02 And apply on a troublesome machine.
The info above came from this page and there is some good info there that might help.
All of this seems like a potentially dangerous thing to do though. I would uninstall the chinese language pack if you aren't currently using it and see if that does the trick.