Issues with MS Network Access Quarantine server

We have been in the midst of deploying Microsoft's Network Access Quarantine server for about 6 months. We have approximately 85% of our remote US users moved over to this new remote access requirement. As we move more and more folks over, we are seeing an increase in the following error: "The quarantine server cannot be contacted - please retry your connection"

This project has been quite a challenge to us overall, but this particular error, we just can't seem to pin down what the cause is. We check for all the obvious: 1)make sure port 7250 is open, 2) make sure you have all the latest security patches 3) if on a wifi router check for firmware updates 4) make sure the service is started and running, etc.
I would welcome advise or a chance to chat with anyone who was successfully (???) implemented Quarantine.