If you're only taking your husband's last name, then the marriage certificate is all you need. The marriage certificate is proof of your name change if you choose to take his last name, you can do that at any point during your marriage.
If you want to change your name in any other way (adding or removing names, change the first name etc), then you change your name at the citizenship stage, as it's free compared to going through court afterwards.
I guess that's why the lady at the SSA was confused, you have been married for so long and could've changed your name at the SSA anytime you wanted during that time with your marriage certificate.