Nero, do you already have a passport under your old name and gender? If not, and if this is your first passport and you've had your birth certificate changed--name and sex both--you can use that as your primary identification. In that case, I don't think you need to worry about documenting your name change or gender marker change. Don't quote me on that, but it should be the case. However, if it isn't, you'll need to document both the name change and the sex change. For the sex change, a court order or the right surgeon's letter ("SRS completed") is supposed to be adequate.
The State Department still does not have anything about sex change on their passport site, but the Transgender Law Center has some good recent info. You should also be able to Google it--look for Passport Bulletin 92-22. You can also drop the TLC an e-mail and see what they say.
And when I was investigating passport info, I used the toll-free number to talk to a live person. It's 1-877-487-2778. I advise you to call on two separate occasions and talk to two different people. Write down the person's name each time. If both people give you the same info, you're probably okay.