Matthew, I believe the region you're referring to is Podolia Gubernia. My maternal grandparents cam from a town there named Krasnoye, in Podolia Gubernia. It was once Russia, but is now Ukraine. There's a genealogy story about a man who lived in three different towns, but stayed in the same house all along. The borders and governments changed, and often the names with them. Try jewishgen's Town Finder.
As another example, my paternal side came from nearby Dumbraveni, Soroki. It was Russia/Bessarabia then, became Romania in 1918, and is now Moldova.
Happy hunting, Molly Arost Staub
Boca Raton, FL
Searching in Podolia Gubernia:
and my ggm Riva's maiden name, for which I've been searching for three decades. She was a midwife in Krasnoye around the turn of the 20th century.