Seiyuu Hiro Yuki looks, sounds, and acts like a 12-year-old girl despite being over 40 years old. Getting his sex right the first time is probably rarer than mistaking it. Also, another seiyuu, Kouki Miyata, says he's been frequently mistaken for a woman because of his high, effeminate voice.
Two female seiyuu examples: Romi Paku is often mistaken for a "New-Half" because of her "husky voice". Also, Wakako "Kujira" Matsumoto plays completely convincing older males (including Orochimaru, who also has his own entry in this page) because she sounds exactly like a guy. Whenever a female character has a suspiciously masculine voice, it's probably her. Actually, she's managed to create double Viewer Gender Confusion situations — at least I have once thought a woman played by her was male because she sounded like a man. Wow.
Hyenas. The females are more dominant, aggressive, and "masculine" than the males. And the females have certain external characteristics that convinced Greek and medieval researchers that hyenas were hermaphroditic.
A lot of birds.
We humans are so used to the idea of human females being pretty that when one first encounters the world of birds, it can be rather jarring. You see, among many birds, the males tend to be pretty while the females are actually rather drab. This actually makes sense; if the female is the one caring for the young, you don't want her to be the one that's all eye-catching. Leave that to the male, who can draw a predator's eye away from the nest.
This is actually invoked in the narrative of Ed Wood's transvestite confession piece Glen or Glenda?.
And with birds that color-wise look more or less the same regardless of gender — thinking of raptors here — it's usually the female that's bigger.
Then there are Chickens. Hens and Roosters are easy to tell apart when full grown but as chicks are indistinguishable. There's an actual job with training involved to be able to distinguish them as chicks.
This was invoked in Pet Shop of Horrors, where Count D invites a group of young society women and young society drag queens to tea at his shop. They watch a pair of feminine-looking dancers — who are in reality, male peacocks.
Parrots, on the other hand, look pretty much the same, and have to be DNA-tested to find out their sex. If your breeding pair aren't, it's often because they're both the same sex.
Human males used to dress up all pretty, and wear makeup and high heels, and this was perfectly masculine. It's only within the last 200 years that fashion forced men to be the dull drab dressers.
High heels were originally used by Persian horsemen to make it easier to stand up in the stirrups without the foot slipping through the stirrup (also why "cowboy boots" have high heels). They were in fact adopted by European aristocrats exactly because of how fucking manly that was perceived to be. Obviously, though, high heels have become quite a bit higher after they became fashionable rather than functional.
Quite a few people thought Chris Crocker (of "LEAVE BRITNEY ALONE!!!" fame) was a girl. A few still do. Although to be fair, he did identify as male to female transgender until 2010.
Because his Author Avatar is genderless and one of the female characters carried the same name as his, Kagami Yoshimizu, the creator of Lucky Star, was wrongly thought as female by many — he lampshaded one when a male proposed to him at a Taiwanese convention, and now it seemed that even the American DVD release also confused his gender, calling him Ms. Yoshimizu...
Christina Aguilera was accused of stealing Lady Gaga's style, and she even admits she didn't immediately know if Lady Gaga was a he or a she.
MAD once ran an article about all the plus-sides to the NBA mandating formal attire for public appearances. One of them was "You can now tell the difference between the NBA and WNBA players." The accompanying picture showed a confused autograph-seeker trying to choose between two tall, muscular, short-haired, earring-sporting b-ball players. However, you could just barely make out breasts on the one on the right.
As one story goes, the California police were looking for a man who had stolen a motorcycle. They found a man and bike matching the description and pulled him over...only for it to turn out to be 3rd Rock from the Sun actress Kristen Johnston, who is quite tall and broad-shouldered for a woman.
The new adverts for confused.com feature the logo as a woman while it was often assumed she was male. Apparently the logo was modelled after the founder of the website, Kate Armstrong, and was always meant to be a woman.
It seems fitting that confused.com would live up to its name in such a way, though.
Youtube guitarist makmakmakochan has pages and pages of comments debating their gender.
Australian singer/performer Courtney Act. Singer of the Top 30 (Australia) hit "Rub Me Wrong". Once made FHM's Top 100 Sexiest Women. Made the finals of the first season of Australian Idol, and even got a record deal out of it. He's a guy.
Granted he is a drag queen, so it isn't too surprising he would create this kind of reaction. And in that vein, a number of drag performers, kings and queens may fall under this trope.
According to Natalie Imbruglia, when she and Daniel Johns were romantically attached, a local paper ran a photo of the two holding hands in public, mistaking it for evidence of her being a lesbian. If you look at older pictures of Daniel Johns, this is sort of understandable, especially ones from when he was clean-shaven with long hair.