I have used AC_NewParent to move users to a new OU for several clients and all are working as expected. The only caveat being that the Account Attribute is not updated until the next AD aggregation.
So that being said, the UPDATE profile still works but it seems AC_NewName is having issues which may be for the reasons you mentioned. I am not sure I want to add AC_NewName as an AD attribute as it would most likely show an warning during creation if it does not exist in Active Directory.
See this post for a different use case where adding cloudLifecycleState showed an error: Failed to Update Attribute