Apparently this is a bit of a bug; in the actual games, Mega-Evolution can still occur even if your Gardevoir has traced Klutz.
It's not really a question of whether Klutz prevents Mega Evolution, but more of a question of whether Klutz prevents Trick and Switcheroo from affecting mega stones (as it apparently didn't in the replay).