I have had the same problem. The solution is so simple:
1- dial *#0*#
2- choose sensor
3- here you will find that the status of your magnetic sensor is: "need to calibrate". So you wave your note 3 in 8 patterns for one or two times
4- and here we go, the sensor status now is calibrated and your problem is solved
P.S.: if you have a problem with *#0*# you can use any compass application or google maps, and then you continue with 3 and 4.
Hope that it helps you