Papyrus is the go-to font when a restaurant wants to make itself look exotic and intriguing! It's definitely a high-street font. I have to say I didn't notice it when I saw Avatar - my eyes were too busy boggling at the 3D spectacle - but had I noticed I would've sniffed a little in disapproval. But then again, I guess it suits the context of the film.
I agree that poor font consideration can unhinge a design but also find myself font-frozen - although I only have the standard fonts packaged with Adobe CS to choose from. Even more daunting is if you're buying a new font for a specific project and have to shell out trusting that you've made the right choice. That's where you really need to do your homework. Also, there's so much choice out there that you really need to keep abreast of new releases and recommendations.