A következő, 2000-2001-es idény még rosszabbul sikerült a Milan, és még jobban Gattuso számára, hiszen a csapat csupán a hatodik helyet tudta megszerezni a bajnokságban, és a Bajnokok Ligájában sem jutott a legjobb nyolc közé, Gennaro viszont immár szinte kihagyhatatlan volt a gárdából: 24 találkozón szerepelt a Serie A-ban, és a BL-ben is rendre a kezdő csapat tagja volt.
A válogatottban viszont nem kerülték el a sikerek: júniusban Európa-bajnok lett a 21 éven aluli csapattal, a nagyválogatottban pedig a felnőttek kontinensbajnoksága után (amelyre az utánpótlás Eb miatt nem utazhatott el) szinte alapember lett: szerepelt a Népstadionban a magyarok elleni 2-2-re végződött vb-selejtezőn is 2000 novemberében, Torinóban pedig győztes gólt szerzett az angol válogatottban Puhl Sándor búcsúmérkőzésén.
A 2001-2002-es szezonra új edző került a Milan élére Fatih Terim személyében. A török mester azonban nem sokáig maradt, hiszen már tíz fordulót követően menesztették, utódja pedig a klub egykori kiváló középpályása, Carlo Ancelotti lett. Az edzőváltás valamelyest felrázta a rendkívül rosszul rajtolt csapatot, amely végül a negyedik helyen zárt a bajnokságban, az UEFA-kupában és az olasz kupában pedig egyaránt az elődöntőig jutott. Az immár kulcsemberré előlépett, 32 bajnokin szerepelt Gattuso tehát harmadik milánói idényét is trófea nélkül zárta, de nagyon bízott benne, hogy a kudarcokat feledtetni tudja a válogatottban, az ázsiai világbajnokságon.
Hogy ez nem sikerült, arról Gattuso igen kevéssé tehet, hiszen nem sok lehetőséget kapott a bizonyításra Giovanni Trapattonitól. Az Ecuador elleni első csoportmérkőzésen 22, a Koreai Köztársaság elleni nyolcaddöntőben pedig 59 percet játszott, mindkétszer csereként állt be.