From the Navy Times:
Navy Department officials are urging the thousands of sailors and Marines forced out of the military because of their sexuality in previous decades to come forward and appeal their discharge — in a step to restore benefits and right a historical wrong.
The Board for Correction of Naval Records can overturn a wide range of records, from counseling letters to detachments for cause, but recently they have been putting the word out to veterans who were separated because of the military’s “Don’t ask, don’t tell” policy — and its previous across-the-board ban — that they can have their discharges upgraded and their reenlistment codes or reason codes changed to reflect a post-DADT world.
In general, BCNR can consider requests to upgrade discharges all the way down to dishonorable, but Thompson said most sexuality-related discharges were honorable or general under honorable conditions, which entitle veterans to all or most benefits.
The easiest cases to overturn are those where a veteran was discharged simply for being gay. If misconduct also came into play, it would be more complicated, but still worth pursuing.