True.
Unfortunately, asides from Worfing or Destroyer or Worlds, there really isn't that much I can think of to justify a new villain being a threat. Maybe he's been pulling the strings this whole time, or he does a terrorist thing with bombs, or he murders some secondary character who is ancillary to the plot, or Red Shirting happens, or we find out that he's somehow in control of an entire private army, or something. Telling the readers that he's a threat is obviously not going to work.
I don't know, maybe I'm just not being very creative right now.