Are you trying with the Windows Store version, the portable version, or the full install version?
The error message indicates that the path to musicbee.exe isn't correct, although there could be more to the message than that.
If you use AVG or Avast, and have not tried whitelisting musicbee.exe, then I'd start there. Your comment that users "change from Avast... isn't really a good suggestion as they claim to be the second or third biggest..." is meaningless. Size doesn't matter. And both have a proven history of messing with MusicBee. So if you use one of them, and refuse to try MB with it whitelisted in your AV software, then you're not going to get much help here. I suggest you try it it and report back.