I suggest you visit the Dallas County Clerk's website. From there, you'll find contact info for the county clerk. You want the Probate Clerk's desk. You can call them, and they can tell you how to get the copies you need.
There's even a downloadable .pdf copy request form. See the links for the clerk's website and downloadable form.
DISCLAIMER: Nothing in this answer constitutes legal advice. If you have a legal question, you should consult an attorney. Further, nothing in this answer shall be construed to have started an attorney-client relationship. No such relationship exists until you sign an engagement letter with the Firm. Visit http://www.shuttlawfirm.com or email firstname.lastname@example.org. You may also call Mr. Shutt, a Dallas probate attorney and wills attorney, at (214) 302-8197 for more information on the topic discussed.
First, please note that I am not your lawyer and you are not my client. Good legal advice requires a meeting with a lawyer in which the lawyer looks at all documents and has a clear understanding of all facts. You cannot rely on this reply as legal advice. Second, of course, I am not licensed in Texas and cannot give Texas legal advice.
The above having been said, the policy must have named the estate as the BENEFICIARY, requiring it to go through probate. I don't know how an estate that doesn't exit yet can be named as an "owner" and so I think that you are misunderstanding something. When they tell you to send a certified copy of the letters, they are saying they want to work with the Executor of the estate because that is the person who has legal authority to act. If you are not the executor then I suggest you have the executor handle this - that's who they want to work with. If you are the executor of the estate - as set out in the letters - then you won't have any problem getting the certified copy. The Court will do that for you for a nominal fee. I suggest you actually drop by the Probate Court Clerk's office so they can do it while you wait.
If all the above doesn't fix your problem, I think you should talk to the lawyer that worked on the Probate matter and together, decide how to proceed.