Preface
So I came across this issue after one of our replication servers went into an inconsistent state. We couldn't get it back on line with a quick fix and decided to reinitialize the replication with a new backup.
The question stated above is not the same problem but does return the same error therefore I decided to add this answer in case other people are looking for it.
It is also an exact duplicate of this question on Server Fault but because that question has a higher ranking in (my) Google results I also posted it there.
What we did
We deleted all our databases on the instance with MySQL Workbench, I restarted the instance and double checked that there where no databases left on the instance.
On the master server we had already started creating a new backup with the script we always use.
Then once the backup was on the failed server we started the import and after a couple of hours it had imported most of the data and failed with these kinds of errors:
ERROR 1062 (23000) at line XXX: Duplicate entry 'dbName-tblName' for key 'PRIMARY'
Operation failed with exitcode 1
We thought okay, maybe something went wrong when creating the backup, I checked out the data in the backup but couldn't find anything wrong. We retried all the steps again just to be sure we didn't miss anything but unfortunately there was no cigar..
The actual problem
The error that is displayed is not the actual insert of the data but the creation of an index. This is why the data was inserted without a problem (we checked) but still generated an error. Apparently deleting all the tables is not sufficient, index data still exists on the server (this might be due to a change in MySQL 5.6 as we never had this problem before). And because the import of these index is somewhere in the middle of the import file the rest of the data didn't get imported.
The fix
We deleted the ibdata1 file and all the innodb_index_stats and innodb_table_stats files in the mysql database folder and then started the instance.
MySQL will then tell you that some system tables are missing
you can find more info on that here
This solved our issue and our server is now replicating as expected.
Hopefully this save some hours for someone somewhere :)