Fixed the problem, turns out if Control Flow Guard (CFG) is disabled, the Connected User Experience service cannot start. This makes zero sense but we are dealing with Windows here so we just have accept crazy nonsense like this.
I've had CFG disabled for some time as I prioritise performance over protection from obscure threats that I'm likely to never encounter, but it seems if I want achievements I'll have to accept it.
So if you're still around OP, try enabling Control Flow Guard, its a setting for Windows Defender in the Exploit Protection section.