I think most run stock brakes with 35s. Check how much you have left on your brake pads. If you want to upgrade, lots have good luck with Dynatrac ProGrips. Kit costs $999
That rolling resistance should be helping him stop though. There's the momentum of the tire (mass * velocity) in the forward direction but also the friction force (downward normal force * friction coefficient of that specific rubber compound and the concrete/asphalt/etc) in the backward direction.If you noticed a difference after changing tires, then a brake upgrade would probably help. You not only have more weight from the larger tires, but also more rolling resistance when coming to a stop.