Can't call Destroy() on two objects

So I have two objects and, when they collide under certain circumstances, I want them to destroy themselves and create a third object in their place. Here is my collision function:

 void OnTriggerEnter2D(Collider2D other)
 {
     if (other.name.StartsWith("Self") == true &&
         other.transform.position != transform.position)
     {
         GameObject OtherSelf = other.gameObject;

         if (OtherSelf.GetComponent<Character>().m_IsPlayer)
         {
             float PlayerSpeed = OtherSelf.GetComponent<Player>().GetSpeed();

             Vector2 FlightDir = new Vector2(transform.position.x, transform.position.y) - 
                                 new Vector2(other.transform.position.x, other.transform.position.y);
             
             bool DidFlee = gameObject.GetComponent<AIScript>().NoticeApproach(PlayerSpeed, FlightDir, 0.5f);

             if (DidFlee == false)
             {
                 GameObject NewCouple = Instantiate(m_CouplePrefab, new Vector3(0, 0, 0), Quaternion.identity) as GameObject;
                 Debug.Log(OtherSelf);

                 Destroy(OtherSelf);
                 Destroy(gameObject);
             }
         }
     }
 }

Unfortunately, this doesn't work as expected. When I run the above code and the collision takes place, only gameObject is destroyed - OtherSelf is left intact. If I comment out Destroy(gameObject), however, OtherSelf does get destroyed. Furthermore, if I comment out Destroy(OtherSelf), gameObject is destroyed and OtherSelf is not, as expected.

Admittedly, both objects will be running this collision function, but I don't know Unity well enough to know if that would be a problem. Would it?

If not, what might be causing OtherSelf to stick around after the Destroy function is called unless gameObject is left alive?