Anomalous paramagnetic effects in dc magnetization were observed in the mixed state of LuNi2B2C, unlike any reported previously. It appears as a kink-like feature for H > 30 kOe and becomes more prominent with increasing field. A specific heat jump at the corresponding temperature suggests that the anomaly is due to a true bulk transition. A magnetic flux transition from a square to an hexagonal lattice is consistent with the anomaly.