The letter Q was never illegal in Turkey. It was just not allowed to be used in names of people/companies etc. due to the fact that it is not in Turkish alphabet.
Häagen-Dazs has always been allowed to operate in Turkey as well as Quiznos Sub and others.
If you wanted a local company, yes, you were only allowed to use Turkish letters in the official name. They didn't actually care what you actually wrote on your signs though.
Official names being Turkish is important because otherwise officials would have needed to be capable of working with all characters in the universe.
I don't think using "the wrong letters" is illegal in the US. What I've meant was it is as wrong as claiming the usage of "the wrong letters" is illegal in the US.