This isn't so dissimilar from A-B Testing, where you test two valid or "workable" options to see which works best for users. It'd probably be a fun thing to test, but there's a very big caveat here.
Long-time users will be used to the old design, and while some will invite change, others may think the old one is better or easier for them, no matter how efficient and perfect the new one may be (and better for them in the long run). People like creating their own systems to work around difficult tasks, and it can be hard to abandon those hacky forms of navigation. So I'd strongly recommend you get a healthy balance between long-time users, recently-added users, and people who've never seen your site before.
I'd also suggest you focus as much as possible on quantifiable results, not just whether someone says they find one thing easier or another (though that's very important). It sounds like you're already thinking that way with success rate, just again, keep in mind that long-time users may be so familiar with the old system that they're successful in spite of its problems.