I've never done this, but speaking as someone who's researched iron liquor as a mordant for dyeing textiles... yes, the rust is key. What you want is ferrous oxide: the rust. The vinegar opens the pores of the leather, and the ferrous oxide reacts with the tannins in the leather, turning it dark.
I want to make some of this myself, so my current cunning plan is to get some steel wool, wet it down and let it sit for a couple of days till it gets good and rusty, and then let it steep in the vinegar.