Hi Jessah,
Since the same affected users can connect successfully to TS01, TS02, and TS03, but fail only when the Connection Broker redirects them to TS04, I would focus the investigation on TS04 rather than the Connection Broker itself.
Please check the following during a failed attempt:
On TS04, review TerminalServices-LocalSessionManager, TerminalServices-RemoteConnectionManager, RemoteDesktopServices-RdpCoreTS, and Security event logs.
Compare the affected users' group memberships and User Rights Assignment/GPO on TS04 with a working session host, especially Allow log on through Remote Desktop Services and Deny log on through Remote Desktop Services.
Verify that TS04 is correctly registered in the RDS collection and that its RDS certificates, DNS registration, and SPNs are consistent with TS01–TS03.
From the Connection Broker/RD Gateway, test connectivity to TS04 on TCP 3389 and compare it with a working session host.
The fact that TS04 shows no corresponding connection attempt during the failure is particularly important. This may indicate that the redirected connection is failing before authentication reaches TS04, so capturing a simultaneous network trace on the Connection Broker/Gateway and TS04 during reproduction would be useful.
If the issue remains intermittent and the logs do not identify the failure, I recommend opening a Microsoft Unified Support/Premier Support case and providing the RDS event logs and network traces for deeper analysis.