Also, since the OP said the spam was from accounts just created, you could add a third threshold (time since account creation before you can submit a story).

By the way there is no reason to pick these thresholds out of thin air - presumably one can look at say the karma distribution of link submitters and figure out what the highest threshold that would inconvenience the least number of people is. For example, I would be truly surprised if 95% of stories were not submitted by people with a karma of 5 or more.