We are experiencing the same exact problem. I believe this issue was fixed with KB3152965.
https://support.microsoft.com/en-us/help/3152965/fix-error-1478-when-you-add-a-database-back-to-the-alwayson-availabili
The KB states that the fix is included in SP3, however we have...