It seems like eliminating the ability for noobs with less than, say, 20 karma from submitting stories would fix this and get rid of a lot of the spam that gets posted.
I know it seems unwelcoming to noobs, but we already have a tiered system where you need N karma for your votes to count, to downvote, to submit polls, etc.
I didn't submit anything for months after joining, which I think is the best way to go. Through actively participating in the comments, I got a good idea of what the HN community was really like.
And even now I don't submit that much (though since I discovered the bookmarklet my rate of submissions has increased). HN isn't about submitting to me, it's about comments (though obviously I realize we need good stories to comment on).
The biggest drawback I see is that it might impact the quality of comments. If users desperately want to hit that submission threshold, they might comment a lot or comment group-think-ily trying to pick up a few points here and a few points there until they hit that threshold.