Auto-leveling errors are most likely the result of a poor connection between the nozzle and the bed.
Make sure that the M3 screw holding the orange sensor wire to the underside of the heater body is tight.
For best results, clean both nozzles and bed rails as explained on this nozzle cleaning guide and on this bed rail cleaning guide.