My wife had to do a smaller version of what you have run into in order to receive her first passport ten years ago. Her issue was that being the forceful, feisty person that she is when she was a child she did not care for the name her parents had given her at birth, so she just changed it. This being around age seven and on. As this was not a legal change through the courts it caused the passport office all kinds of fits as nothing matched. The best evidence turned out to be an affidavit from an uncle that it was her despite the conflicting names.