EV was great in the league. He had the results. No doubt there.
But the fanbase also had CL aspirations and his humiliations there were never going to be forgotten. Yeah Koeman also got blown out by PSG in the CL, but losing on a 3 goal advantage looks worse.
And the bigger thing was that Valverde's team didn't show any long term vision of success (aside from Fati's debut). A lot of that is on the board for not providing the right signings, but the team played slow, uninspired and relied on too many old veterans.
Everyone could see that the team would eventually fall off a cliff with the way they played once you squeezed out the last bit of juice from the Messi-Suarez duo upfront and also the likes of Pique, Alba, Busi, Rakitic.
Koeman has shown a potential future that could be exciting and also bring results.
Koeman uses lot more young players which is something fans want. Though i don't think that mean the future is safe.