I was also receiving error code 85010013. After some investigative work I found a solution.
Here is how I managed to sync a Nokia Lumia 920 Windows Phone 8 device to an Exchange Server 2007:
1.- Install a Trusted Cerificate (mine is a self-issued one) into your phone. I installed it by copying it from my PC into my Skydrive and then downloading into the Documents Folder of my phone.
2.- Ask your Exchange Administrator to do the following: At the Exchange Server Management Console, access Microsoft Exchange/Organization Configuration/Client Access. You will find an Exchange ActiveSync Mailbox Policies list. One of them is named "Windows SBS Mobile Mailbox Policy (ServerName)" At General Tab, check at the Allow non-provisionable devices box. Also check if you want to allow attachements to be downloaded to device.
3.- Set your phone to sync to exchange by accessing Mailbox setting, adding your exchange account information trhough the Advanced option. Note: do not set a password to unlock your phone before setting your exchange account. If you did so, erase this account information, deactivate the screen unlock password and set your exchange account at your phone again.
I wonder why it is so criptic to get this done.
Good luck!