I'm throwing Jill Scott out there. She can sing, both studio and live. Try the track "He loves me" or "Gotta get up" with 4hero.
Corinne Bailey Rae, she's simply awesome, great live and unplugged too.
Maaya Sakamoto, Japanese, but she has a few tracks in English too.
Santessa, kind of like a modern Sade.
Late night alumni
Laleh, has some tracks in both in Swedish and English, try out the track "Live tomorrow"
I'll also second Feist and Jenny Lewis.
If you like a couple of those I'd like to know what you think I might like