I frequently use the term "the other day", and have never thought it unusual.I have picked up a habit from my Mom. She is from Mexico. I don't know if that is a Mexican thing or just her habit, but she always says "the other day' to mean anything from yesterday to many years ago. I do think that Mexican culture may view time a little more loosely than we do here. Now i say it.
I have even heard it pronounded "tyudder day".