"Believable aliens" means they should not talk and act like Midwestern 20th century Americans, yet they shouldn't be too alien, because the reader won't understand them at all. It's better if their societal model is based on some human cultural situation, or animal behavior -- and Taylor Anderson, who has a Master's degree in history says that pretty much any societal model you can dream up, such as a matriarchal cannibalist society, has a precedent in human history. Extremely alien aliens might work in a very short story, since the reader may be able to read it without getting too confused or losing interest. "The Dance of the Changer And The Three" by Terry Karr was given as an example of such a story.
Speaking of human models for alien societies, Chris Roberson suggests we look no further than the Japanese society. He thinks there are more differences between Japanese culture and ours, than there are between any science-fictional aliens and us. To interact with Japanese, he had to be taught how to do do smallest things in certain ways, so as not to offend them inadvertently. For example, there is a right way and a wrong way to accept a business card from someone. It is mandatory that you pause and read the person's name in the card. To tuck it away without reading it would be rude. Japanese is endlessly fascinating, he says. It's like watching alternate history. Even though they've experienced the same recent major events as the Western society, such as World War II, they've spun it into something completely different.
Joan Vinge thinks that may have been the case in the past, but in the era of globalization Japanese aren't as opaque to us as they used to be. Still she thinks James Clavell "Shogun", a novel of 16th century Europeans' exploration of Japan, is an excellent first contact story.
Taylor Anderson, Ann Aguirre, Joan Vinge, and Chris Roberson in the Aliens panel.
An aside. Not long ago, as I wrote about Lithuanian science fiction fandom, I mentioned being mildly annoyed that every cultural discussion was accompanied by a refrain "Orientals are soooo different from us! Don't try to understand them, lest you go crazy!" Yet I didn't find myself rolling my eyes at this discussion, probably because it approached those differences -- which are real, no doubt -- without employing that vague catch-all notion of spirituality. Once you start down the "orientals are sooo spiritual, and their spirituality is sooo different" track, that's when my eyes glaze over. Otherwise, yes, I agree, there are many cultural differences, and in some ways they are opaque to us.
Back to the panel. So, human societies and animal behavior as models for your aliens? Ann Aguirre chose the latter. She based her aliens on praying mantis. This has an advantage that when she gets fan mail asking how do her aliens have sex -- and she gets those letters at least once a week! -- she can tell them to Google it. Hint: sexual cannibalism. :-)
Pictures from ArmadilloCon 2009 are in my photo gallery.