3rd Party Watch Apps Cellular Trouble

I have been having trouble with 3rd party apps not being able to connect to the internet via cellular on my Series 4 Apple Watch. The system apps can all connect fine (Maps, Mail, Messages…) but 3rd party watch apps (that DO support connecting over cellular) rarely can (Carrot Weather, Outcast, Dark Sky…). I have tried wiping and resetting my watch and that fixes the problem for a day or two then they stop working again. I also had my watch replaced (for another reason) and am having the same problem on the new watch. Apple Support has no idea what is wrong but I am hoping one of the bright minds here might! Anyone else having this issue?