May 2001, Nutter joined Aldershot Town, then of the Isthmian League Premier Division. He made his debut in Aldershot's 3–1 home victory over Enfield on 18 August 2001, and scored his first goal for the club shortly after in a 2–1 away win over Heybridge Swifts. Nutter made 19 appearances for Aldershot during the 2001–02 season, scoring twice. He also made eight appearances for divisional rivals St Albans City during a two-month loan spell. He spent a month on loan at Conference National club Gravesend & Northfleet in November 2002, making four appearances. During the campaign, he scored three times in 21 appearances for Aldershot, in a season that saw the club earn promotion to the Conference National after winning the Isthmian League Premier Division. Nutter played regularly during Aldershot's return to the highest tier of non-League football, making 28 appearances in all competitions and scoring once in a 4–2 away victory over Bishop's Stortford in the FA Trophy in January 2004. Aldershot missed out on back-to-back promotions, losing on penalties in the play-off final to Shrewsbury Town. Although Nutter did not play in the final, he did feature in both legs of the semi-final as Aldershot defeated Hereford United on penalties. During his three years at Aldershot, Nutter made 68 appearances in league, FA Cup and FA Trophy fixtures, scoring six times. Grays Athletic Ahead of the 2004–05 season, in July 2004, Nutter signed for Conference South club Grays Athletic, managed by Mark Stimson. He made his Grays debut on the opening day of the season, playing the first 57 minutes in a 1–1 away draw against Hayes on 14 August 2004. Three days later, he scored his only goal of the season as Grays beat Redbridge 4–1 at the New Recreation Ground. In Nutter's first season with Grays, the club achieved promotion by winning the Conference South title by 23 points. During the same season, Grays also won the FA Trophy, beating Hucknall Town on penalties in the final at Villa Park, with Nutter playing the whole match. As a result of Grays' promotion, the 2005–06 season gave Nutter another opportunity to play in the Conference National. He played regularly during the season as Grays finished third in the league. His only goal of the season came in the Conference play-off semi-final second leg, as Grays lost to Halifax Town 5–4 on aggregate. Shortly after the play-off defeat,