KT Tunstall is a very unique sort of one-woman band - she has a moderately folksy/bluesy pop sound (think a less upbeat Sheryl Crow, perhaps), but the sound alone isn't what's so special. While her music taken on its own is very good, you'd never know how truly impressive she is unless you scrounged up some video.
The album's not here ("here" meaning "in the US") yet, but I heard an intriguing interview with this artist on NPR the other day. It's well worth a listen.