
Quoting
Mr. Knowitall
If you're eighteen, then it should not have been possible for you to get a Social Security number without having submitted your original birth certificate to the Social Security Administration. It seems more likely that your mother submitted a birth certificate with her name, then later added your father's name to your birth certificate through an acknowledgement of paternity. Ask you mother and, if that's what happened, see what records the Registry of Vital Records and Statistics holds of the original birth certificate and AOP.
You should follow the instructions you received from the SSA before proceeding with your name change -- take in your documentation and try to get the issue corrected. Once the issue is resolved you can proceed with a name change that the SSA will recognize, rather than potentially making your situation even more complicated to resolve.