You would have to apply to the Board for Correction of Naval Records. You have been discharged more than 15 years ago.
You would have to prepare a petition and argue that you should receive a discharge and why, and also explain why it has taken this long to apply. The BCNR has a three year statute of limitations. But unlike the DRB they can waive the time bar for "good cause."
So, you've got a difficult path. But I am curious about the events that appear to have got you apprehended for UA and then discharged.
There seems to be a discrepancy between what your lawyer "told me" and the OTH?
You can contact me by email to arrange a more detailed review and evaluation of your case - it's free.
www.court-martial.com; www.court-martial.us.com; firstname.lastname@example.org 703-298-9562, 800-401-1583. Answering your question does not create an attorney-client relationship.
Because this happened so long ago, you will certainly have difficulties ahead. First, there is justifying why the BCNR should consider there to be good cause for you appealing beyond the normal 3 year statute of limitations. Then, there is the issue of trying to compile corroborating evidence to support your claims - documents and letters from witnesses (who remember the events). With regard to what your lawyer told you... For as long as I have been practicing (since 1995), there has been a myth about automatic discharge upgrades after 6 months. In my career, there have never been such automatic discharge upgrades, despite this persistent myth. You can certainly request a discharge upgrade, or even to have a discharge overturned, but these requests are not granted in a high percentage of cases, and they certainly aren't automatic.
In order to have your characterization of discharge corrected or upgraded the only option you have it to apply to the Board for Correction of Naval Records in Washington D.C. I currently have a case pending before the Board and am very familiar with the process. Based on the facts you provided in your question, I think you have a strong case. Feel free to give me a call to discuss further. I would like to help you. First consultation is always free.