Have them connect to the IP address instead of the name. I've had the same thing happen off and on for some users with no specific resolution. It just started working again. Some users could still see it listed and others couldn't. I thought it was related to their ping for a while, but still haven't determined what caused it.