Hi Cparkeram,

I understand that users couldn’t sign in Lync with the “a personal certificate error”. Is the full error message “There was a problem acquiring a personal certificate required to sign in”?

If it is, to troubleshoot the issue, you can refer the KB article: http://support.microsoft.com/kb/2604176.
You can also refer the article:
http://office.microsoft.com/en-us/communicator-help/troubleshooting-lync-sign-in-errors-administrators-HA102759022.aspx

To further troubleshoot the issue, I would like to collect the following information.
Have you added your domain to Office 365 recently?
Have you updated user’s sign in address?
Are the users created from Office 365 directly?

Thanks,
Monica Tong