Your reader was only trying to help by spotting the misplaced modifiers. Try:
Dressed in plain clothes, they walked down the street like any other travelers with somewhere to go.
I wouldn't do this, either. Starting a sentence with the modifier is awkward.