Are you using layered textures? What are the dimensions of the texture you're painting? Have you set filtering to "None" in the file texture node? Your UV shells are also quite spaced out. If you rearrange them, each shell can have more space within the dimensions.