I have experience in this area before with both overstayer and Schengen visa rejection. My girlfriend got her visa rejected from the French embassy before due whatever reason that the embassy didn't really clarify. But she got the stamp the same as you had. And we had to cancel the whole trip which some of the transportation costs cannot be refunded. We talked to a lot of people and people got mixed experience. Some say that she had to re-apply with the embassy that rejected the visa, because embassies don't share information, if you got rejected from French embassy, German embassy might not know why but they can only see the stamp that visa has been rejected and they will likely reject the visa.
So, what we did was to just re-apply with the French embassy. When we got inside the embassy again, she had to answer a couple of questions with the lady in the embassy and the decision took a bit long. You just need to be honest and explain everything. We explained everything and told them that we booked everything with the return ticket back home, but we didn't know why the visa got rejected the last time. In the end, they approved my girlfriend's visa and we can enter French border without any problem.
Now for overstaying, my friend got her visa rejected from the UK embassy due to the type of the visa (Short-stay) cannot be extended inside the UK (but she didn't know). That led her to be an overstayer because she applied ten days before the visa expired, and the decision took more than that. So she had to leave the country but with the record. So, the rule for overstaying is if you voluntarily leave the country. You will be banned on entry for 1-3 years. During the time you cannot apply the visa, or it will be rejected for sure. In my friend's case she waited for a year and then apply for the visa again. And she had to be interviewed for a half an hour but in the end her new visa was approved. However, if you're forced to leave the country you'll be banned on entry for 10 years. During the time, you cannot apply for any visa. In your case, I guess it should be one year same as my friend. But every time you enter the border the immigration officer will ask a lot of questions even though you have the visa, and they can reject your entry and send you back home. My friend got asked some questions, but she could return without any problem.
http://www.euro-dollar-currency.com/overstaying_schengen_visa.htm
Hope this helps.