I am a brand new user and was pulling my hair out with this "The Server 'Omni Sync' requires authentication". For me I discovered the problem and the solution as follows, thanks to my use of an additional automated login system other than key chain.
When I registered my user name it had capitals in it. Apparently and most bizarrely the Omni focus registration system converts all capitals in your user name to lower case and makes the use of lower case mandatory. Very helpfully, it does not tell you this and Key Chain and similar products record the User Name as you entered it, rather than as Omni Focus decided to change it to, i.e all lower case, and make case sensitive.
Having changed my User Name to all lower case I no longer have an issue with "The Server 'Omni Sync' requires authentication". The fault is not with Key Chain or sandboxing as far as I can tell, it appears to be in Omni Focus itself.