So it turns out there is caselaw on this subject (despite what I said earlier), or at least the big picture. It doesn't have to do with the initial naming decision, as in the song. But if a boy wants to change his name to Sue, at least in some states, he may have to show that he is "a transvestite or a transsexual and, if a transsexual, whether he has undergone a sex change operation and is now anatomically and psychologically a woman" -- since otherwise such a change "would be fraught with danger of deception and confusion and contrary to the public interest" -- or at least that Sue "is regarded as a male name in this or some other culture."
Thus, changing your name from William to Veronica or from Stephen to Steffi is not allowed without such a showing; likewise Johnny to Sue. (Application of Anonymous, 587 N.Y.S.2d 548 (City Civ. Ct. 1992); (In re Bobrowich, 2003 WL 230701 (N.Y. City Civ. Ct. 2003).) But the trend for people who really are transsexuals -- which William-to-Veronica ultimately proved to be, but Stephen-to-Steffi apparently wasn't -- is to allow such name changes. (E.g., Matter of McIntyre, 715 A.2d 400 (Pa. 1998); Matter of Eck, 584 A.2d 859 (N.J. Super. 1991).)
Thanks to Timothy Sandefur for the pointer.