On Samsung devices like i9100 (Galaxy S3) or N7100 (Note II) you can do the following if you have root permissions:
On Android Terminal App or adb shell do:
$ echo 0 > /sys/class/sensors/proximity_sensor/prox_cal
$ echo 1 > /sys/class/sensors/proximity_sensor/prox_cal
The zero resets the actual calibration offset.
The one does an auto calibration (read sensor value, set offset to this sensor value, write calibration offset to "/efs/prox_cal" which is read while device is booting).
Best for calibrate your sensor is to keep it dark, the glass have to be clean and the sensor free (so that the sensor doesn't measure anything).
The calibration offset is stored in efs, thats why you can make full wipe and use other ROMs without the need of recalibration.
You can check the running config by:
$ cat /sys/class/sensors/proximity_sensor/state
The first value is the calibration Offset, the second one is the sensor threshold (threshold is set at compile time).
Open *#0*# to see "sensors" and check if your proximity sensor is now working properly.
Because in Kernel code (copyright by Samsung) for the device driver is somthing like this autocalibration, i bet that there is a secret menue or code that does the calibration too. But until someone discovers this secret we have to have root permissions to do a proximity sensor calibration.