They were creating a gaming system that could track a person's movements in real time, and they wanted to see if the researchers could help improve it.
With a tight deadline looming, Shotton suggested a radically new approach. His supervisor, Andrew Blake, made what he now jokingly refers to as "my pivotal contribution to this work" which was to tell Shotton that "what he was doing would never work."
A month or so later, Shotton was showing Blake a prototype of that idea, which would prove to be a key part of Microsoft's groundbreaking Kinect motion-sensing device for Xbox and Windows PCs.
It was, Blake said, typical of Shotton's calm determination and no-nonsense approach to his work.
"He doesn't make a lot of fuss," said Blake, who directs the Cambridge lab and recently accepted the role as the first director of the UK government-funded Alan Turing Institute in London. "He just sort of gets on with things quietly, and then you look on and realize how much he's done."
This week, Shotton will be honoured as one of MIT Technology Review's Innovators under 35. The distinction goes to exceptionally talented young innovators whose work the editors believe has the greatest potential to transform the world. Previous winners include Google co-founders Larry Page and Sergey Brin and Facebook co-founder Mark Zuckerberg.
For Shotton, it is yet another moment in a career that has already exceeded his expectations.
"My career has been a series of good fortunes," he said. "Hopefully I've managed to do a little bit to capitalize on those good fortunes."
From the BBC Micro to Microsoft Research Cambridge
Shotton first developed an interest in computer graphics as a child, growing up in the United Kingdom during the heyday of the BBC Computer Literacy Programme designed to encourage kids' passion for computing. He received his first computer, a BBC Micro, for Christmas when he was around eight.
"Having that early exposure to coding was really key," he said.
Flash forward a few years. Shotton was finishing up his university degree in computer science and trying to decide what to do next when some friends suggested he get in touch with Blake at Microsoft Research about an internship.
Shotton was immediately hooked. He went on to pursue a PhD in computer vision, under the guidance of Blake and Cambridge University Professor Roberto Cipolla, and motivated in large part by a desire to work at the research lab full time.
Shotton said that was partly because of the intoxicating buzz and energy he felt at the lab, and partly because he wanted to build a career at a place where he could see his research turn into products that would empower people to do more.
"I'm really keen to see the projects I work on out there in the real world," he said.
That was in the early 2000s, at a time when computer vision specialists were just starting to work on incorporating a branch of artificial intelligence known as machine learning into their work. At Blake and Cipolla's urging, Shotton began looking at what he could do in this nascent field.
Machine learning uses algorithms to create systems that can learn based on data that they receive. With computer vision, that means that the system can learn to recognize objects, such as cars, horses or people's faces, after seeing training data that shows the characteristics of those images.
From Kinect to Handpose
Shotton was showing some promising results incorporating machine learning into computer vision when the lab was approached in 2008 about the project that would come to be known as Kinect.
His radical idea: Use machine learning to teach the system to recognize parts of human bodies. It was in many ways a completely opposite approach from what the team had been trying so far. But Shotton, who was a post-doc at the time, felt like he had nothing to lose in giving it a try.
When Shotton presented his results, Blake said he was astonished to see how well it worked.
Shotton and other Microsoft researchers ended up playing a key role in bringing Kinect to market. The system has been a differentiating feature for Xbox, and it's also been used in countless other areas, from improving healthcare to making meetings more productive.
Shotton, who is now a principal researcher at the UK lab, has continued to build on that work with a more recent project called Handpose, which aims to track hand motions to millimetre precision.
It's a system that could be used in any number of applications, including directing robots in dangerous environments, translating sign language into spoken word and interacting with virtual realities.
Looking further into the future, Shotton said he is excited to see what the recent breakthroughs in artificial intelligence will mean for every aspect of our lives.
He noted that some of these developments, such as personal digital assistants and self-driving cars, have the power to fundamentally reshape how we live our lives. His work is putting him on the front lines of those changes.
"Creating something that really empowers people to do new things – that really excites me," he said.
He's also hopeful that artificial intelligence will start being used to help computer scientists like him more quickly and effectively write software.
"Software development is still really hard, despite decades of development leading to radically better languages, tools and processes," he said. "One thing that could really accelerate technology's progress would be intelligent agents that help you code software."