Could you incentivize people that upvote new items that ultimately cross some threshhold (front page/votes) such that their upvotes translate into some kind of karma or reward points of some sort? The earlier you are as an upvoter the bigger the reward? Of course that may just incentivize people upvoting everything in sight :) Perhaps historical upvoting patterns on the New Page could be incorporated to penalize that kind of behavior. Just throwing it out there. I do agree, I occasionally browse the new page but there is just so much cruft there that looking for the gems is time consuming so I generally just (lazily) wait for them to hit the front page.

Edit: Once again bitten by reading HN comments before the article as he proposes something along these lines in the post, doh! :)