Why was a soldier in uniform trying to buy cigarettes in the first place? Service people should have pride in service and uniform. Smoking/buying cigarettes in public in uniform is akin to glue-sniffing in uniform, or being drunk in uniform - not illegal, but very definitely bad for the public image of the services. The only place that it should be acceptable to smoke in uniform is when out of public view - e.g. in the mess or, when off duty on overseas ops - though I would prefer that to be banned too.
If (god forbid) I ever had to work in an off-licence or tobacconist, I would refuse to serve anybody in a uniform representing a public service too (i.e. police, military), and I would give them a good earful too about representing their uniform.
The same people you preach to have more than likely been to war and been shot at just to protect your right to free speech. Remember that.