Madeleine Peyroux: She's back. But is she bothered?

The drummer strokes out shuffle-rhythms with his brushes; there's a real Hammond organ with turned Corinthian columns, and the bearded young man playing it - coaxing out fairground noises like The Band's Garth Hudson - is a complete star. By the time Madeleine Peyroux (you pronounce it Peru), starts to sing the opening number she's co-written with Walter Becker of Steely Dan and her record producer Larry Klein (Joni Mitchell's ex), you're totally converted. And I didn't mention the double-bassist or the avant-garde female violinist, or the way the sound was so beautifully hushed that everyone leaned forward in their seats like the brightest students in class.

Whatever you call this kind of music - there were songs by Leonard Cohen, Fred Neil, Serge Gainsbourg and Charlie Chaplin as well as Ms P's originals - it's a long way from Parkie's jazz-lite, even if Peyroux continues to enunciate as if she imbibed Billie Holiday's Lady in Satin with her mother's milk. There's clearly a lot more to her than a perky thirtysomething white woman (born Athens, Georgia, 1974), sounding like a knackered black tragedienne, although the voice does appear genuinely fragile.

To cap it all, Madeleine Peyroux had not only turned up here at Bristol's Colston Hall but looked decidedly chipper, if notably averse to Barbie-clothing or showbizzy trappings. She may be the AOP (Adult-Oriented Pop, and I just made it up) version of Holden Caulfield.

Last year, you'll remember, Peyroux was supposed to have "disappeared". Her British record company issued a statement saying they were hiring a private dick to find her, although it turned out she was back home in New York, fed up with waiting in the green rooms of naff British breakfast shows doing endless promotion for her hit album, Careless Love. Having bailed out of a previous brush with success after her 1996 debut Dreamland, "Am I Bothered?", could, you feel, be her watchword.

This performance started well and got better. It's partly the unforced, natural vibe of Peyroux and her brilliant band; partly the repertoire of her forthcoming new album, Half the Perfect World, which is more contemporary and singer-songwritery than Careless Love. A lot of the pleasure was also down to the incredible Sam Yahel, on organ and piano, and Jenny Scheinman (who plays spiky jazz with Bill Frisell) on violin. At heart, perhaps Peyroux herself is still the rather erratic Paris busker she used to be. But good songs, delivered with sensitivity, intelligence and charm, are what an awful lot of us want.