On paper, Faithless shouldn’t work. One key member, Rollo Armstrong, doesn’t sing or play an instrument and doesn’t play with them live – and after the first couple of years, he stopped doing interviews, too, preferring to be seen as an enigma.

Although in recent years he’s laughingly come to realise that perhaps no one cared enough to create a mystique around him, he has remained part of Faithless, but only when they are working in the studio. Live, the action revolves around a classically trained pianist turned house music DJ, Sister Bliss, who is now also mother to an eight-month-old boy. Which perhaps isn’t the easiest thing for a band that has sustained its reputation for the past 11 years by touring relentlessly.

And finally, you have rapper Maxi Jazz, a devout Buddhist who this year celebrated his fiftieth birthday, and who grew up with reggae, soul and jazz and still maintains he’s confused as to how he ended up in an electronic dance group.

You can’t imagine record labels queuing to sign up a new band with these credentials, and if they entered The X Factor, they’d be laughed off in the first round. Yet here they are, still making exciting, relevant music while their peers in the field of dance/electronica have long since fallen away.

This year they followed up the massive, unexpected success of their greatest hits collection Forever Faithless with a new album inspired both by the birth of Rollo’s second child and Bliss’s first baby, and by the rise of global terrorism and the conflicts in Iraq and Afghanistan.

The themes of To All New Arrivals are no surprise to their loyal fans. Faithless have never flinched from the big issues, never ceased to say what’s on their mind even when it seemed like commercial suicide, and have always managed to find a positive message thanks to Maxi’s strong Buddhist beliefs.

We meet them for the interview in Le Voile Rouge, a tented club/bar/restaurant right on the beach in the middle of the Cannes Film Festival. They’re here to launch ‘I Never Stop’, a track they’ve created to accompany an innovative short animation film made by the avant-garde design group Paranoid in partnership with Coke. The track is available to download via iTunes and Coke’s own music web-site.

After you made your No Roots album in 2004, you were talking about quitting, or at least taking a long break. Yet here you are with a new album.

Maxi Jazz: Yeah, you can put that down to Blissy. She’s one of those people that doesn’t know how to relax. Which is why she’s got her baby on tour with us, and is getting absolutely no sleep as well as fretting about the set and the songs. She loves to fret!

Sister Bliss: I’m alright. I’m loving every second of being a mum, though I’ve not written any new music yet. And I’ve got help. My nanny is amazing.

Maxi Jazz: Don’t listen to that bullshit for a second! She’s not getting enough sleep. So anyway, she woke up in March, heavily pregnant, with the title To All New Arrivals going round in her head and the feeling that we just had to get on and do this album. And of course as soon as our kid got pregnant, we had a deadline – any album that we were going to do, we had better do by the time she gave birth or it wasn’t going to happen for a while.

Sister Bliss: This line, To All New Arrivals, kept going round my head, and from it all these themes emerged. So I rang Rollo up and I said, “I’ve got an idea for an album, and it’s about what’s happening at the moment.” It’s a title that had lots of messages…

Maxi Jazz: To all new arrivals to the country, meaning immigrants. But also to all new arrivals to a new way of thinking, a new consciousness – because the old way of thinking has bought us to this, and nobody likes it. So for me, that’s what the title means: welcome on board, we now think this way as opposed to that way, and we’re going to try and do something to change things.

Sister Bliss: It’s double-edged, there’s a duality – which is what we were trying to get across in the album. We live on an earth full of the most wonderful, mesmerising, genius things, and pain and misery and destruction as well. I felt that it was a new perspective on the same central message we’ve been trying to get out since the start.

And how would you define the Faithless message?

Maxi Jazz: If you listen to luminaries like Martin Luther King and Ghandi, they say the same thing, over and over again. The message does not change. It’s always the same: love yourself, love each other. That’s it. Global warming, pollution, war, all of that is cured once you start to love yourself, and then as a result of loving yourself, start loving other people. Because those things you hate in yourself, you hate in other people. That’s why there’s so much conflict. Every single human being has so much brilliant stuff within them. But you only make true what you believe. So if you don’t believe you have genius, then you can never manifest it, even though everybody has it. For instance, I believe anybody can sing, if you believe what you have in your heart. Look at Bob Dylan – he can’t find the note, much less hold it.

You’re always perfectionist. You didn’t have huge expectations of the greatest hits album Forever Faithless, yet it stayed in the UK charts for most of 2006.

Maxi Jazz: How funny is that? It’s caused me a serious amount of confusion, but then I’ve been confused about Faithless almost as long as I’ve been in it. It was most confusing how well that record did. I’m a great believer in shelf life, that everything has its shelf life. Everything is effective up to a point. And once past that point, you have to stop. And I’ve been aware of that with Faithless for the last three or four years. I’ve felt that people will get bored of us soon, and I don’t want to be the one dragging myself onstage when everyone is going, “Christ! Not them again!” I’ll be gone long before that time happens. And it confuses me that you put out the greatest hits at the record company’s insistence, thinking that’ll be enough, it’s been ten years, and it turns out people want it. Lots of people! It’s astonishing to me that after the Forever Faithless album, we seem to be more popular now than when we were popular. We should have been dead along with The Prodigy, Underworld and Leftfield and all the others that have hit the floor.

With Faithless, nothing ever seems to turn out as you expect it to…

Maxi Jazz: Ah! That’s very true!

I was thinking about your 200x track Mass Destruction, which you assumed would be ignored in the US but which actually built you a while new following there. And then the video for Bombs, which I thought was a beautiful, very commercial single, got banned by MTV.

Sister Bliss: They didn’t quite ban it. I think there was a watershed on it, because they didn’t want to show it in the morning when kids were going to school. It just won an award, by the way. It got Best Electronic Video in the video equivalent of the Oscars in America. Which is great!

Maxi Jazz: There’s a scene at the end where there are some schoolchildren, and soldiers are coming through their classroom and they’re screaming and obviously frightened and upset. And I think MTV had an issue with school-kids seeing that. So it wasn’t a ban, as such.

You’ve always put a lot of thought into your videos, and collaboration is something Faithless has always done with its music. Tell me about the video collaboration you’ve just done.

Sister Bliss: It started with this ground-breaking video, which uses seven different kinds of animation. Coke asked us to write some new music for it because they were attracted to the message of Faithless – which is positivity. In our messy, scatty way, we have come to stand for something. And because it came from an artistic place rather than a commercial, crude place, we felt it was quite interesting. When we saw examples of the animation, we thought it was outstanding. And for us, working with pictures like that was lovely, really inspiring. To me, it’s about this little alien being that comes into contact with the beauty of nature and then the energy of the city. We just tried to make the music move along with the animation. We like to create a lot of different textures and moods in our music, so we got a lot of different grooves going along with some sitar flavours because the beginning of the animation is quite exotic, like a Rousseau painting. The animations refer to different periods of art all the way through. It’s quite ambitious. The track is an instrumental right now, but it probably will have lyrics, eventually. We’ll see what the response is to it. It might even end up on the next album!

I was talking to The Chemical Brothers recently, and they were saying how hard it is to find new sounds now, because so much has been done.

Sister Bliss: But they’re the masters of it. That track ‘Galvanize’ on their Push The Button album... they’d obviously sat there for a year looking for fresh sounds for that song. Incredible!

But you seem to manage that too.

Sister Bliss: I think because Rollo isn’t a musician, he responds to things like a child. And also we’ve always loved cold, glacial sounds. There’s something about house music, electronic music that is glacial but warm and melancholic at the same time. Like Afrika Bambaataa using Kraftwerk on ‘Planet Rock’. Rollo just has a natural attraction to that.

Are you enjoying playing live again? It’s always seemed the way you communicate most directly with your audience.

Sister Bliss: It’s been a joy, recently. And the shows are getting bigger, so there’s obviously something in there that people need. We did a gig for Oxfam in Berlin recently, and then we were in New York the other week and it’s like we have a new audience out there.

Maxi Jazz: When you play songs like ‘Mass Destruction’ and ‘We Become One’ in America, something comes over you because they are the people that need to hear this, and they want it so much.

Sister Bliss: The show in Berlin was just incredible. We did a press conference with the African rapper Emmanuel Jal, who was a child soldier in the Sudan, then a refugee. He was adopted by an aid worker who was then killed in a car crash. This man had lived through hell.

Maxi Jazz: And a different hell from your dole cheque not arriving that week.

Sister Bliss: It made me feel that Maxi’s lyrics are still important, and they kept running through my head as we did the press conference. This is what happens when people don’t love each other: they’re dispossessed, their parents are murdered, their sisters are raped. It was so inspiring, just amazing to meet someone like that, the kind of person our songs have always been trying to tell the world about. It got us all fired up again.

The new Coca Cola Faithless Alu bottle is now available in selected nightclubs nationwide. Download both the track and the animation for free, and see the band talking about the project at www.coke.com/faithless. The Coca Cola iTunes on pack promotion runs from May until the end of August - Coke and iTunes will give away songs from the iTunes Store (www.itunes.com) in over 2 billion promotional packs of Coca-Cola, Diet Coke and Coke Zero. For more information visit www.music.coca-cola.com.