It should be where you said you've looked.
Go into the Control Panel,
then to Regional and Lanugage Options.
When in that, go to the Advanced tab, and then change the language there. This should change menu's or at least it says it would.
I would try it myself, but I don't want to change it to French, only to realise I don't know how to get it back
I think It'd work