It seems to me that whatever villainous entity was being used in Trek was based on what scares us, the audience. You can see the distinction between The Original Series and Next Generation because there was enough time between those two to see the line.
We were scared of the Klingons (they were mysterious) in TOS, but by the time NG came along we were getting along and coming to respect each other.
The Borg was the fear of being swallowed by the huge machine and becoming just a cog in the wheel of progress without identity.
In the new movie the villain represents the fear of the terrorist, the individual that has only ties to some ambiguous goal and whose true intent is to simply destroy.
I don't think the Borg ceased to be scary because of overuse so much as because we as an audience are simply not as effected by them as say we are by Nero right now. In five years all this could be completely different and there would be a new scary villain.