Aside from the new look of the Klingons and the new Starfleet uniforms, I think the biggest criticisms by fans were in regards to the movie itself being too slow, too long, and not having enough action. In comparison, the redesigned Enterprise was received favorably by all but the fiercest fans of the original design.
Which is odd when the same fans claim that the new Star Trek movies have too much action and that old Trek was all intellectual and stuff.
I think the negative reaction to TMP's pace (and among my fellow pre-adolescents at the time, it has to be said, lack of space battles) is what led to every subsequent Trek movie having to be an action film, for good or for ill.