I had to unloosen the cable that connects the two brakes to replace the tires.
Now, if I pull the two brakes together with my hand and tighten the screw, the outter brake (ie. the one at the longer end of the wire) is at the right distance from the rim, but the inner brake touches the rim:
'89 Fuji Saratoga, '97 Schwinn Mesa SS, '07 Felt F1X, '10 Transition TransAM, '11 Soma Analog SS
When you say you had to loosen the cable, did you do this by un-hooking the noodle, or did you loosen the clamp bolt? Learn to un-hook the noodle for wheel removal. You shouldn't need to loosen the clamp bolt to remove a wheel. If you did, maybe you now have it clamped too tight. If that is not the case, and it wasn't rubbing before, I would guess the wheel isn't seated completely into the dropouts or it wasn't seated when the brake was originally adjusted. Check that first. If that doesn't take care of it, this page Park V-Brake Service will show you which screws to turn to balance the brake.
I never learned to ride a bike. It is my deepest shame.
fietsbob has the right idea - make sure the wheel is fully seated int he drops before you adjust the brakes. If the brakes were reasonably well adjusted before changing tires and there is no reason to suspect the brake arms got bashed or snagged on something (enough that would result in the brake moving past its normal operating range and bending the return spring) then the wheel alignment is the prime suspect.
Also, the picture seems to show the left hand brake arm (non-drive side) as the one that is too close to the rim, and also very high up in the brake track and close to the tire. The other side seems to be lower down and not touching the rim, and when the brake is actuated, the pad will go even lower, possibly partially sliding off the edge of the brake track. This could also be caused by the wheel not being in straight.