Hello again, @Joe Harrison !
There was an issue with one of the dependent services that was causing both the Starting.../Stopped issue in the portal and resulting in the "GatewayTimeout","message":"The gateway did not receive a response from 'Microsoft.LabServices' within the specified time period."
error when using PowerShell.
This has since been resolved and we have performed a root cause analysis to ensure that it doesn't happen again. Thank you very much for bringing this to our attention!