Rehash is a fair criticism because it makes the franchise seem one note. Yes Nolan's use of the Joker was amazing even though it had been done in 1989. The other side of the coin is Lex Luthor ALWAYS being used in Superman movies. The Man of Steel film is breaking that trend. However when you use and reuse the same villain or plots over and over it makes the franchise seem stagnant and uninteresting. Batman and Superman have many other villains, but the Joker and Luthor are both the most recognizable. The same thing can be said about Trek. The Borg, Klingons, Romulans are Trek's most recognizable villains. So the idea to capitalize on their notoriety is what drives the decisions to use them to get patrons in seats in theatres.
With STID we have a third movie in a row that is thematically similar to the TWOK. The other two being ST 2009 and NEM. The fans asking "can't you do something else?" is a fair question.
Aren't all those superhero villains basically 'rehashes' of the comics? I'm not sure though, I hardly know anything about comics.
I do agree with you that we need a different type of villain for a change... Therefor I think the Borg would be great! They're like a swarm, like space zombies bent on assimilation... not a vengeful soloist like Shinzon or Nero was... (I do think STID was a little different though, with Adm. Marcus being the real villain...).
I see a great story somewhere, involving Q, Borg, Klingons, even Khan as a new crewmember.......