Just in case anyone else has or gets this problem, I have found a workaround (I don't consider it a solution):
It seems that Windows has a default keyboard switching shortcut: Ctrl+Shift (NOT Windows+Space, as stated on some sites). By using that combination, my new users can switch keyboard layouts. I then went back to the first two users, where I can change the switching method, and changed that from my preferred LeftAlt+Shift to Ctrl+Shift.
At least all users can now change keyboard layouts and use the same key combination to do so. It's just a shame they all have to change from the combination they are used to from the previous Windows, as the facility to choose the switching method works for only some users. This must be a bug! (If anyone knows differently, do please correct me:)