Hello,
AddNew() creates a new object and adds it to a Collection. The Collection acts as a factory. So calling AddNew() in order to move something is wrong.
All model constituent classes in the API have an attribute specifying their owner, eg Package.ParentID, Attribute.ParentID, TaggedValue.ElementID.
In order to move anything from one Collection to another, you don't manipulate the Collections, but change the owner reference in the object you want to move.
So simply change the EmbeddedElement.ParentID from OldElement.ElementID to NewElement.ElementID, then call EmbeddedElement.Update() to write the changes to the database.
Note that the EA API will not automatically update any references. So after you've made the change, your OldElement.EmbeddedElements and NewElement.EmbeddedElements are both out of sync and need to be .Refresh()ed.
HTH,
/Uffe