Brady didn't really become a great QB until after winning a few super bowls. His TD/INT ratio was always worse than 2:1 during that run, and he never passed for more than 235 ypg. He was basically a pretty good QB backed by a solid ground game and an excellent defense - much like Russell Wilson, who also gets the 'great' label from some, even though anyone actually watching the games can tell that the Seahawks wouldn't be a playoff team without their defense.
Back then QBs weren't putting up the video game like numbers they put up today. Not many QBs put up 2-1 TD in INT numbers. In 2001, just 4 did. In 2002, only 5 did (and Brady was one of them). In 2003, just 4 did (and Brady was at 1.95 to 1).
In 2002, Brady was 6th in the league in passing yards with the most TDs of anyone in the league (28).
In 2003, Brady was 6th in the league in passing yards and 10th in the league with 23 TDs.
In 2004, Brady was 10th in the league in passing yards and 6th in the league with 28 TDs
In 2005, Brady was 1st in the league in passing yards and 3rd in TDs.
In 2006, Brady was 7th in the league in passing yards and 4th in TDs.
In 2007, Brady was 1st in the league in passing yards and 1st in TDs (NFL record)
The defense was good, but not always great. The Russell Wilson comparison isn't close to valid IMO.
NE Defensive ranks
2001: 24th in Yards against, 6th in points allowed
2002: 23rd in Yards against, 17th in points allowed
2003: 7th in Yards against, 1st in points allowed
2004: 9th in Yards against, 4th in points allowed
2005: 26th in Yards against, 17th in points allowed
2006: 6th in Yards against, 2nd in points allowed
Also, lets look at the Patriots' leading receiver these early years. None were very good. Brady wasn't working with a great WR corp and hasn't with the exception of the Moss years.
2001: Troy Brown
2002: Troy Brown
2003: Deion Branch
2004: David Givens
2005: Deion Branch
2006: Reche Caldwell
How many pro-bowl WRs did he work with for those 6 years? 1 (Troy Brown in 2001).
Lots of numbers... but I'm bored.. and I'm right.