If you only knew the "gestures" I've made at my computer over the last 5 years dealing with this issue .
OK, so upon applying this fix to my work VM this morning, I found a new wrinkle. The basic cause & steps to fix are the same, but the starting configuration has a minor difference.
This is with a brand new Parallels VM created from scratch with Windows 8.1 a couple weeks ago. I installed LabVIEW 2014 and a couple other applications, but it's basically a "clean" VM. I'm posting this since I imagine there will be other people stumbling through here over the months/years with brand new VMs – more than those of us with VMs from Parallels 4, to be sure .
Anyway, when I went to Control Panel >> Change Input Methods dialog, the only input method installed was the "United States (Apple) - Parallels" one.
In order to switch to a different one ("US" in my case), I had to actually Add the "US" layout, then Remove the Parallels one.
Interestingly, in this case I did not need to restart Windows afterward. So that's more like Jonas's experience.