We show that the magnetization in color-flavor locked superconductors can be so strong that homogeneous quark matter becomes metastable for a wide range of magnetic field values. This indicates that magnetic domains or other type of magnetic inhomogeneities can be present in the quark cores of magnetars.