The problem is not that the Changed event isn't being fired; as long as the same class definition (with the setter that raises the event) is used for the deserialized object (with DataContract serialization that isn't a requisite), the event will be raised. What's happening is that the deserialized object no longer has the handler attached.
You cannot serialize or deserialize event handlers; at the very least, you shouldn't. Because they may point to references other than the current object reference, and because the deserialized object is a new reference in what is probably a different runtime, event handler references from the serialized object are useless on deserialization, because the reference will no longer point to the expected object in the new runtime's heap.
The solution is a little easier than your workaround, but based on the same idea; implement custom deserialization behavior in the parent that reattaches the handler to the child's event:
<OnDeserialized()>
Private Sub OnDeserializedMethod(ByVal Context As StreamingContext)
AddHandler Child.Changed AddressOf Me.Child_Changed
End Sub
This avoids the memory and time costs of instantiating a new Child just to destroy another one, and should do the same trick. It is technically possible to do this on the Child, but the Child would require knowledge of its Parent using a backreference. It's also a little backwards; generally speaking, event raisers don't "grab" event handlers, but instead are given them by other objects that contain or know about the handlers and the event.