I have a 28mm tyre on a bike that should max out at 25mm. Its a really close fit, and I have a similar problem to you when the brake quick release is open - namely when the brake pads are further apart, your brake arms are wider and the metal up near the pivot point is in a different place.
In your case the new unworn pads are thicker and pushing the arms apart, eating up the last millimetres of clearance.
The proper fix would be to put a smaller tyre on, but that's annoying.
In my case I ended up filing the center of my brand new tyre where the mold join lines were, which gave more clearance.
In your case, look at your brake pads and see if you can swap around or remove some washers. The Drive Side brake pad holder seems different height to the left one, but that could be an artefact of the carpet pattern in the background.
Another option is to add some wear to the brake pads with a file, to provide a little more clearance. You might want to buy some thinner low-profile pads for the back wheel and save those ones for the front wheel where you're not having any problems.