Verifying user for password changes

How do you go about verifying that the user on the other end of the phone is who he/she claims to be? Because of HIPAA compliance, we are currently redrafting our policy and are trying to balance expediency with security. We can’t have people sitting around idle until we can verify them, but at the same time we need a really good method of determining this. I suppose we could have their supervisor send us an email requesting it, but then the early morning folks have to wait around a couple of hours.