It's hard to describe this as exactly a "cover". It's so heavily reworked, and sung in a different language, that it's pretty unrecognisable. David Byrne describes it as flamenco music meets Sonic Youth. And there's definitely something to that description.
Anyway, the whole album is amazing, but here's a taster with 'Manhattan'...