The sentence in the title
I was not used to their accents.
contains one verb -- was -- and it's past tense.
The phrase used to in that sentence is not the past tense idiom.
It's another idiom, pronounced the same way /'yustə/, but with a different meaning. Be used to means the same as be accustomed to.
This used to idiom is a predicate adjective and requires an auxiliary be verb (that's the was)
- She is used to taking the 9:12 bus. = She is accustomed to taking the 9:12 bus.
- I will never get used to their accents.
The other used to idiom doesn't use an auxiliary verb; it is an auxiliary verb, with a special sense.
- I used to live in Chicago. = I lived in Chicago at some past time (but I don't live there now).
So, if you see a be verb in front of used to, it's the "accustomed to" sense, not the past sense.