Since to problem occurred only after the hinges were replaced, and presuming the door had no other issues, the fix will need to be only with the hinges. There may have been a cardboard shim behind the old hinges to tweak them in place, many doors need this as time goes on. That is all you should need as well.
Cereal box cardboard or similar material work best since it is relatively thin. If you put something too thick behind it, the hinge problem will go away, but you will have the door hitting the jamb on the other side.
I slice the cardboard into 1/4" strips the length of the hinge, in your case 3 1/2" or slightly shorter. Loosen the screws on the hinges you need to adjust one at a time on the jamb side and slip the cardboard shim behind the hinge and push it in far enough to flush up with the jamb. Tigthen those screws.
I add the cardboard to one side only, the jamb side. Adding it to the door side will show an unsightly gap, whereas when you apply it on the jamb side, the trim and hinge barrel hides the gap. If the gap needs to created all the way through, in other words, on all hinges, then the procedure is simple, add shims at all hinges. I find that sometimes the hinges need more than one shim, sometimes it needs to be doubled. Then I take the cardboard, cut it 1/2" wide, then score it lightly in the middle, so it will fold like a hinge on the score and I have a double thick piece that is easily controlled as it is inserted.
If you find that the gap is tighter on the top end or perhaps it is the bottom end, there is nothing wrong with adding a double thick on one and a single on the other. Another tip I always use is, and this is only if you have a door with 3 or more hinges. Remove the center hinge pin(s) first. The door leaf is typically considered straight, very rare when the edge of a door is not. Jambs can be installed very crooked without knowing it, for the center pin will hold the jamb "straight" I have removed the center hinge pin before on a door I had to correct, and had the jamb shift a 1/4" on its own without touching it to make it move. This was the worst one I seen, and I seen various movement to lesser degrees too. A 1/16" is nothing, but not desired but if you do what I suggest, it can be no deflection from straight. The door will work the easiest if all hinge pins are in a straight line. If they get out of alignment the door will work stiff, or noisy.
Back at the shims. with the center pin removed, gap the jamb the way I described above with the shims to make the door work freely, remember no middle pin. After that is accomplished, and if needed, loosen the screw on the center hinge and apply the needed amount of shim(s) to the center hinge. Tighten the screws, open and close the door a few times to make sure the hinge is settled into its new position well before you drop in the pin. Adjust one last time if you need to get it just right, the set you pin to finish the job.
Note: Be CERTAIN that the new hinges are set properly in their mortices before you start this, many time a hinge will lay over one edge of the mortice or the other and yank around the door fit that way. So much for that detail.
No, the cardboard does not have to be all the way across the setting of the hinge. The shim as I describe it will eliminate the possibility of hinge binding.