Firstly, if you were not notified of the case, then you have not been served with the legal action. If you were not served, there is a legal question as to whether or not the case has been properly commenced against you. Also, since you are the biological father of the children, there's no way that the case could proceed without your receiving notice unless it proceeded under false pretenses, based on the assertion that your address was unknown and that there was no way to contact you at the time of filing. Since these are fundamental legal questions which affect your legal rights as to your children, and a change of custody involving same, you should contact legal aid in the state of New Mexico where the case exists, or alternately, contact court directly and ask for court-appointed counsel.
Understand that there is no way that you're going through complex interstate custody litigation by obtaining online advice. You need legal counsel. However, take heart. Your legal rights are superior to those of any third parties, since you are the biological parent. Unless there is something fundamentally wrong with the case itself or with you which would preclude you from acting as custodian, you would normally be first in line to have the children. Nonetheless, you will need to hire an attorney and get into court. Good luck.
The answers to questions provided in response to the request for assistance are general in nature, and reflect information which is primarily based upon general legal principals, and may additionally reflect Ohio principles of legal practice, as this is the primary location of this Attorney's practice. As with any legal advice, the advise is general in character, and should not be put into practice without specifically consulting your local counsel, who will possess far more insight into the applicable standards and laws of your specific State, your case's specific issues and the local Rules of Court and practices of the specific jurisdiction your legal action is governed by. You are specifically instructed : Do not proceed without first discussing this matter with your own local Attorney. This Office does not provide free legal advice by telephone. A 15 Minute Consultation can be obtained at no cost for certain types of legal cases, but to obtain same, an Office appointment is required. Provision of the answers to general questions does not constitute an act of representation, and the Attorney shall not be deemed to accept employment based upon the responses contained herein. The reader is advised that they utilize the general suggestions contained in the responses at their own risk, and under no circumstances should they disregard the advise of their present local legal counsel based upon any suggestions or opinions contained herein. Also, the bast method to discuss a case with an attorney is to do so directly, by scheduling a formal consultation in their office, bringing with you at the time of the meeting all of your relevant paperwork, including any contratcs, any Orders from Court, decrees, complaints, pleadings, etc., and any other relevant information for the attorney to review. General information via the internet is no substitute for an actual meeting with an attorney. The advice provided on line in response to the limited information is provided without charge. It is also provided without the benefit of face to face discussions, so before you act--consult an attorney in person.