Finally found a solution for this issue, and as always it was much more simple than I was thinking.
First, I reinstalled the SSL certificate according to Godaddy's instructions.
This solved my SSL problems, but I still wasn't able to complete a sync with a mobile device.
The solution, was to publish another Exchange Web Client Policy for activesync.
This means there is a policy for both OWA and ActiveSync.
This ultimately solved the problem I was having.