Horcruxes are rare (and then seven come along at once...) and only a few people know about them.
But when was the last Horcrux before Voldemort's? 50 years before him? Centuries? Millennia?
I'm going to limit this question to "among the known users of Horcrux's".
In which case the answer is: 2600 to 2800 years ago.
But... I'd say it's sufficient to say more than 2000 years ago.
The most recent Horcrux-er other than Voldemort is Herpo the Foul1.
Depending on how loosely you want to take the description of Herpo the Foul who was said to be a wizard in "Ancient Greece", which is traditionally described to be 600 to 800 BC.
There are no other known creators of Horcrux's.
While there is only negative evidence to support this (that Herpo was the 2nd most recent user), the HP Wiki notices the same thing. So, while there's no canon, the negative evidence is generally accepted as proof.
While the Dark Lord’s method of creating multiple Horcruxes was previously unheard of, making one Horcrux seemed to be at least somewhat known, since there was quite a bit of information about it in Secrets of the Darkest Art, including how to protect them, how Horcruxes could possess others if they get emotionally attached to them, that the soul can heal by remorse, and how to destroy them.
“This is the one that gives explicit instructions on how to make a Horcrux. Secrets of the Darkest Art – it’s a horrible book, really awful, full of evil magic.”
- Harry Potter and the Deathly Hallows, Chapter 6 (The Ghoul in Pyjamas)
We don’t know who the most recent one before the Dark Lord was, but from the sheer amount of information on them in Secrets of the Darkest Art (which was quite an ancient book), there would have certainly been enough people who’d done it for that amount of information to exist.
We do have an idea who the first one to make a Horcrux is. In an interview, J.K. Rowling says that Herpo the Foul was the one who’d created the first Horcrux. He therefore almost certainly wasn’t the most recent to make one before the Dark Lord, unless all the information in Secrets of the Darkest Art came from Herpo’s one experience, which seems incredibly unlikely.
SU: Oh, Jo, but those "horcruxes", though, I tell you, they're so much to ask still about those, you know?... I mean, who, okay, we have to know. Who created the first Horcrux? Was it Grindelwald? Salazar? Who did that?
JKR: D'you know what, I've got a feeling it was Herpo, which is H-E-R-P-O.
SU: Herpo the Foul?
JKR: ... Herpo the Foul, exactly, yeah. Yeah. But you know wizards would've been looking for ways to do exactly what Voldemort did for years, and some of the ways they would've tried would've killed them, so I imagine it... well, there's huge parallels. Splitting the atom would be a very good parallel in our world. Something that people imagined might be able to be done, but couldn't quite bring it off, and then... and then people started doing it with sometimes catastrophic effects. So that's how I see the Horcrux.
- PotterCast Interview, (December 17th, 2007)
However, the only thing we can say for sure about whoever was the most recent to make a Horcrux before the Dark Lord is that they would have been a Dark wizard, otherwise it would be unthinkable to them.
Seeing as how the point of a horcrux is to prevent them from dying and letting people know would kind of ruin that prospect if someone destroyed the horcrux, I would have to say that we would be very unlikely to know who else used horcruxes.
For all we know it could be relatively (keyword being relatively) common for anyone willing to commit murder to make a horcrux. Even if they didn't do it on the scale of Voldemort its pretty tempting to have that sort of protection from death. (Obviously this is all speculation on my part)