tl;dr: The game was dominated by spells from 1995-2003, so the philosophical change began ~8 years ago in 2004.

I believe Ice Age [1995] marks the beginning of the "spells win" era - but I'm not familiar with what sort of tournament scene existed before that point. This peaked with the Urza's Saga block in 1998, largely considered the single most unbalanced set ever printed. Mirrodin [2003] was meant to be a return to creatures, and almost succeeded. Unfortunately, a small number of severely broken cards warped the format in to something that was still focused almost entirely around combo decks.

I believe Kamigawa [2004] marks the first block that wasn't dominated by combo/spell strategies, and actually valued creatures, although "Magic 2010" [2009] was probably the first block that truly captured the new "creatures win" focus of the game - from then on, it's pretty much indisputable that the focus of the game had changed.