Yes, you need to do this at a military base that has an ID office. Bring your current ID, court order changing your name, and proof of surgery if post-op. Some military bases are open to the everybody, such as army reserve units. If a guarded base is the only one available, some people register as quests and ask for directions to the ID office.