I actually didn't realize I used this formula for my headlines until someone pointed it out here on HN. Now that I notice it, it saves me so much time to search for an alternative.
I don't know if you need to change much Andrew -- there is nothing factually incorrect or misleading about your headlines. Perhaps the same "unfunded startup makes it big anyway" formula is overused but its a damn good formula and there's a reason it works so well. And its not like your headlines are like Mashable -- the quality of your content is consistently very high and very thoughtfully done.
Though your interviews are unlike other interviews in traditional media, they are totally helpful and inspiring for those of us slogging away who haven't quite crossed the line yet. I'm a big fan, especially of the fact that you don't let go of questions very easily and that you do nice things like provide transcripts or make your interview videos embeddable.
FWIW, the title really puts me off. Similar titles that put me off:
"How I built a startup in N hours"
"How I built a business with just $N"
where N is designed to be small to increase click through.
In society we're all looking for too many short cuts. Too many easy fixes. Fat? Nah - don't exercise and eat healthily, get a diet pill!
Also the whole rags to riches story is a really tiresome angle to take on things IMHO. I'd say that most startups are built by people without any money :/
(Having said that I do really like the interviews you do. Very interesting).
Great interviews by Andrew all the time. The range of questions Andrew covers are phenomenal. Just finished listening to one of his old interview with founder of Twitpic.