Yeah applocale and Japanese region are the first solution one should try solution to pretty much every touhou game (to the point that you should just do it by default). But I'm new to windows 7, so I wasn't really sure how to do it properly. As Serela stated, it's under controlpanels->clock,region,whatever->Region and language->Administrative tab (that's the part that I didn't try->change system locale.
That fixed it for me =).
Surprised reinstalling worked for you, it definitely didn't sound like the kind of crashbug that a reinstall would fix, especially if we coincidently got the same problem with the same enemy!