I think a tropical bird makes sense, given the two landscape pics we've gotten so far.
But I don't think it's a toucan, like a popular fanart is suggesting, as I think a beak that large would be... fairly obvious, even right now, and unless they're intentional taking the beak out, it might just be a different bird.
Some birds I like for Lele so far have beenhttp://www.artfullbirds.com/Silver-beaked%20Tanager.jpg
= Silver Beaked Tanager
= Tropical Mockingbird!
They're both South/Central American species. And I also have this feeling that if the Lizard is really colorful and color-changing that the bird actually might be less ostentatious, to not be obvious when he changes, or effectively the exact opposite of Banjo (fairly dull) and Kazooie (SO BRIGHT).