Thank you to everyone who has replied thus far...a few points of clarification.
1) We are indeed running in pull mode, but I've always assumed that a client checks in immediately after every reboot.
2) -> Lumia@720 in this instance I'm only talking about workstations, since our servers only get rebooted on patch nights, we don't normally "see" the issue. As far as the workstations go, when there is no green dot the clients typically show "offline" in the troubleshooting menu.
3) The situation only presents itself if a customer signs in directly after a reboot...as Brian mentioned, maybe the services have not yet completed their tasks before the desktop is ready.
All that said, this is new for us with RU5 as of the past couple of months...prior to that, it was as Chetan mentioned, less than a minute to get a green dot regardless of how quickly after a reboot the customer signed in.
I'll test a few more machines as suggested, and wait patiently for RU6 to see if anything changes. As I previously mentioned, this could be entirely on our end and something our networking folks have added to the mix.
All the best,
-Mike