I originally posted about this on the O365 forums, where you can read all of the details. Apparently I'm not allowed to post links, so you'll have to add http:// to the text below to view the details:
community.office365.com/en-us/f/166/p/296097/904032.aspx#904032
They got stumped and sent me over here. I've tried completely uninstalling and reinstalling Lync (including deleting the Keychain entries and such) and I'm still having the exact same problem. Any other ideas?