Gogol Bordello : Gypsy Punk rock. If you like the Pogues, or the way they combined their country's traditional music with a punk/rock aesthetic, you will probably like this.
Also,
J.U.F. (Jewish Ukrainian Freundschaft) : lots of the same people, but it's dance music, with "Balkan, Turkish, dancehall, Rai and flamenco beats." I can't stomach much that's called dance music, but the first download on that site ("Gypsy Part of Town") is really cool.
Balkan Beat Box too - again some of the same guys. And again, they do interesting things with traditional Eastern European folk sounds.