Matt,
Assuming the wheel is true, I'd next check the tension on each of the front brake's arms. There's a little screw that presses on each of the v-brakes' linear springs, and that can sometimes cause an arm to go in and out of adjustment when braking and can cause periodic rubbing on one side.
In my experience, I have never found Shimano v-brake springs to have even tension from the factory, so usually start by backing off the screws evenly, then disengaging the springs from their little pegs and gently bending them so the tension is equal, then turning the screws inward as desired to set overall spring tension. Doing it this way ensures the arms stay equally tensioned. As mentioned elsewhere, I detailed my procedure to a Shimano rep at a race one time, and he said he did the same with his.
Hope this helps.
Best,
Dan.