From what I read it might be a Cortana issue because for some unfathomable reason their normal app search on the start menu is now "Cortana", but if I understood correctly Cortana isn't even available in all regions? I don't know how this is supposed to work - is there a cut down search service that is called Cortana but isn't Cortana? I have no idea and Microsoft docs on this are terrible.