I discovered it's nothing to do with the SSO permission. It was actually a problem where the users didn't have access to then SB2 or RP environments, but the Access box is still checked after the refresh his complete. Once I unchecked/rechecked the Access box and Saved, they are able to log in. Utterly ridiculous. User Access after Sandbox refreshes has been a problem for as long as there have been sandboxes.