He is a part of an alien species with different sexual characteristics than humans. He only went by Alice because he thought it was easier for humans to pronounce, but later decided to go by Andy after he found out Alice was a girl's name.
Bob meets Alice thinking that "Alice" is a man, only to be distraught when she's revealed to be the real deal. (Only an inversion of the basic version: The actual trope is not concerned with which gender Alice actually is, just if the reveal upsets Bob)
Discussed: "This chick I'm going out with right now is pretty cool. She knows sports, likes watching Baywatch... uh, Jeff is a girl's name, right?"
"I don't know if I'm going to bother watching tonight's episode, TV Guide says Bob finds out his girlfriend Alice was born male and we all know his reaction is going to be so insensitive and horrified that it'll make pretty much every transgender or trans-friendly viewer cringe."
Implied: Bob is shown following Alice around with heartsin his eyes. After Alice turns out to be Andy, Bob stops speaking to him.
Deconstructed: The reveal puts a heavy strain on (or outright breaks) Bob and Andy's relationship. For one thing, Bob cannot forgive him for having lied to him about something so important, and Andy ends up heartbroken because he just wanted to get close to Bob, not even as a romantic interest, but as a good friend, and now he just hates him guts.
Played For Laughs: "Alice" and Bob walk into a room together, the implications are clear, but seconds later we hear Bob scream "OH MY GOD! DUDE! YOU'RE A DUDE!" and see him run screaming right through the door trying to get away from the newly-revealed Andy.