A quick update:
By reducing the compression on those backups, I dropped the CPU spikes from 95%-ish down to 90% or less most of the time, and that has had the effect of eliminating the rejected users.
That confirms that the trigger was failing (timing out or otherwise I don't know, though that still seems most likely to me) due to CPU pressure, despite being about as streamlined and skinny as it is possible to be.
I think this should serve as a warning to anyone considering a logon trigger - be very careful on any server where you are likely to experience CPU pressure at any point: the trigger may prevent new connections during such times.