They had clocked him right back. They were wearing Millwall football tops, he recalls, "big burly white dudes with shaved heads". Minutes later, hearing them running back his way, the actor feared the worst.
"I tense up, I don't know what's going to happen, but they run up and say, 'Mate, respect for Four Lions, can we please have a picture?'"
It was a lesson in things never being quite as they seem, one that is laid out in gripping style in Ahmed's new film, The Reluctant Fundamentalist. Adapted from the bestselling novel by Mohsin Hamid, and also starring Kiefer Sutherland, Liev Schreiber and Kate Hudson, the Mira Nair-directed political thriller is out next week.
The 30-year-old Londoner plays Changez, a young man from Pakistan living the Wall Street dream. Happily dividing his heart and mind between his new life in America and his family in Pakistan, Changez seems to have bridged the class, cultural and generational divide. Then September 11, 2001, happens and everyone's world, including Changez's, flips on its axis.
"I loved the book and I could really relate to the character in the way that he grows up between cultures and classes." While the story touches on immigration, he says, it's equally about the way his generation live their lives "on iPod shuffle".
"No-one gets a job at 16 and stays in it until 60 any more, we're connected to more people simultaneously than ever before, whether online or on our phones. We wear so many different hats within one day, one week, a lifetime."
The star of Four Lions, Shifty, Ill Manors and Black Gold was also keen to work with the director of Salaam Bombay and Monsoon Wedding. Having worked mainly on low-budget, low-fi films, he found Nair's attention to the visual details of a scene fascinating. Then, of course, there were his co-stars. On meeting Sutherland for the first time, Ahmed did wonder if it was a good time to start quoting lines from 24, but he managed to confine himself to congratulating him on Young Guns. Working with Sutherland and co was like having a masterclass in filmmaking, he says. "Every week I had a different person to learn something from. Kiefer has been doing it for so long he really understands the craft of filmmaking, it's fascinating to see him on set."
One of the film's key scenes involves Changez coming home to New York from a business trip abroad. It is just after 9/11 and he is halted by airport security. I wonder if it took Ahmed back to 2006, when he was part of a group stopped at Luton Airport after returning from picking up an award at the Berlin Film Festival for The Road to Guantanamo.
It wasn't the same, he feels. At Luton he was more baffled than anything else and could not see any purpose in the questioning. He could look at the experience and put it down to a few individuals. When it happens to Changez, it is a sign that life, the system, had changed forever, he says.
"It's always a bit more soul-destroying to feel like you are up against a system rather than a few individuals."
When Ahmed speaks about the film's global themes he sounds every inch the Oxford philosophy, politics and economics graduate that he is (he went to Oxford after winning a scholarship to a private school). He laughs when I point this out. "I do find it interesting, I think a lot of people do, I don't think you have to be a politics buff to look around and go, 'Hang on, we're living in the middle of a financial crisis, what was the thinking that allowed us to get here,' or 'Hang on, we're living in constant fear of attack, what's the thinking, the journey, that has brought us here?' People are a lot more switched on and the idea of there being 'political interest' and 'the rest of life' is dissolving."
Which brings us back in a way to Four Lions and the Millwall fans. When the idea for a comedy about a gang of mates turned wannabe suicide bombers was first mooted it looked as if the writer-director, satirist Chris Morris, was letting himself in for another Brass Eye-style backlash. Ahmed was in no doubt, however, that Morris knew what he was doing. They had talked about the idea for more than three years.
"I understood from getting to know him that the man is obviously a genius, he's a hilarious, warm, special person and I didn't really have any doubts about how the project would be received."
He was more unsure if a comedy was what he wanted to do after Shifty, the acclaimed British drama directed by Eran Creevy (whose latest film is James McAvoy's Welcome to the Punch) about a young dealer trying to break out of the life. In the end, Morris persuaded him and Four Lions went on to win a Bafta.
Ahmed got his start in youth theatre, and it is an opportunity he is grateful for to this day, judging by the way he speaks about others being given similar chances. Britain is well placed, he says, to be a storyteller for the world. There's a "but" though.
"We will only succeed in building on our Adeles and our Danny Boyles and our Stephen Daldrys and Irvine Welshs if we continue to support the arts and empower the next generation of storytellers."
Ahmed divides his time between acting and music. When we speak, Riz MC the rapper has just finished his second album. His first, MICroscope, featured a collaboration with Plan B, his director on Ill Manors. The music and the acting feed each other, he says, and other things besides. MICroscope, for instance, started off as an electronic rap album, became a theatre show, a short film then a video game.
This reluctance to be boxed in extends itself to his choice of acting roles. While he feels he has played a diverse range of characters, he says he is frequently asked in interviews if he is concerned about being stereotyped.
"Changez is very different to the character I played in Ill Manors who was really different from the character I played in Trishna who was really different to the character I played in Black Gold who was different from the character I played in Four Lions. I don't feel that any kind of narrow stereotypes are representative of the work I've done, nor the range of the audience that work has found. I've played lots of different roles and they've connected with lots of different people."
In the next few years he wants to move into directing, first by making a short film then developing it into a feature. As for what else it could become, he's keeping an open mind. "People are interested in fresh stories and there are new ways of getting stories out there, so let's see."
The Reluctant Fundamentalist opens at Cineworld Glasgow and Cineworld Edinburgh on May 10.