Use of Lagrange multipliers produces a saddle-point problem,
$$ \begin{pmatrix} A & B^T \\ B & 0 \end{pmatrix} \begin{pmatrix} u \\ \lambda \end{pmatrix} = \begin{pmatrix} b \\ 0 \end{pmatrix} $$
As you've noticed, many preconditioners break down for this sort of system. One can use direct solvers that support pivoting, but if you want iterative solvers, a common flexible strategy is to use PCFIELDSPLIT; see the factorization (Schur) methods in the Users Manual section on Solving Block Matrices.
Note that the fact that you cannot use conjugate gradients because this problem is not positive definite. You can use MINRES with some preconditioners, but it's sometimes more effective to use nonsymmetric (usually block triangular) preconditioners.