We demonstrate that the interplay between a nonlinearity and PT symmetry in a periodic potential results in peculiar features of nonlinear periodic solutions. These include thresholdless symmetry breaking and asymmetric (multi-)loop structures of the nonlinear Bloch spectrum, persistence of unbroken PT symmetry even after the gap is closed, nonmonotonic dependence of the PT phase transition on the defocusing nonlinearity, and enhanced stability of the nonlinear states corresponding to the loop structures. The asymmetry and the loop structure of the spectrum are explained within the framework of a two-mode approximation and an effective potential theory and are validated numerically.