I just had my rear tire replaced at an -- admittedly shady -- bike shop, and now the upper part of the rear brake is rubbing against the lower part of the tire:
The yellow dust on the picture results from the friction between the tire and the brake.
However, the wheel is the same as before replacing the tire and the axis seems to be correctly centered:
Brakes are lowered as low as possible. I'm really at a loss here, so I'll be happy to hear any suggestion.