Well, this one must have really stumped the Experts! In any case, after much troubleshooting and careful consideration of the entire environment, I think that my problem was due to the fact that my TSG was pointed to TS 1, which is part of my 2-server TS Farm (load balanced).
Some how, after being authenticated, I think that the access to the RemoteApps is somehow being load balanced. That would explain why some people could connect and others could not - same session on different TS being reconnected. It would also explain why different users were affected by the issue after a TS reboot.
To test my theory, I made the available RemoteApps on TS2 identical to TS1. Guess what? Everyone who had not had access before suddenly had access. It's been running for a couple of weeks now so I am confident that this is the solution. Also, when I initially configured the RemoteApps, they were identical on both servers. However, as time progressed, we had made many changes to the TSG and you can only point it to one of the servers, not to the farm (it errors out). During those many changes, the two servers were no longer identically configured.
I will be closing out the question with this answers as the solution.