I was recently setting the data export service for the first time and ran into the above error.
We were using the export service to populate a ODS database with data from CRM and since in Azure SQL you can't have sql statements traversing databases, all the tables needed to live in one database, both CRM and other.
Instead of using a prefix, we wanted to use a custom schema to identify the different sources.
So the wizard setup looked something like this:
Now following the documentation here: https://technet.microsoft.com/library/mt744592.aspx#Prereq_DES , I was under the impression, since the user actually has rights to create a schema, that the process would create my new custom schema as its first step.
It doesn't! It just fails with the unhelpful "Insufficient Write Permissions to destination store" error. Since I know my user had the relevant permissions, I chased my tail for a few days and even resorted to logging a call with Microsoft.
I eventually thought I would go through each step I expected the wizard to be performing in the background to see if the permissions were in fact there, once I created the Schema, it occurred to me that perhaps it needed to exist before running the wizard, so tried again to run through the wizard and Hey Presto.. no more error and I now have a working data export service.
I've given the feedback to MS that the documentation isn't really clear on the requirement to create any custom schema beforehand manually, or that this is, in fact, a bug. Hopefully, it will be resolved in a coming update. If not, hopefully, this post helps someone.