Well... in answer to the personal question. I ended up submitting my first paper about a year and a half into my PhD. For various reasons, it took around two years before it got accepted.
As a side note, I encountered a problem in my undergrad which I was unable to resolve until towards the end of my PhD - which I've now submitted for publication.
As for how much experience... actually, I don't think all that much experience is required - it is more important to find a suitable problem. It needs to be largely unresolved, but have a reasonable chance to be open for attack without years of study. If you're interested enough in the problem, as you study the problem and read other authors' articles, you will gain the necessary experience.
