You might have missed this statement on the Device Tracker doc page:
However device tracker will only look for global settings under the configuration of the first configured platform
Do you have multiple device_tracker platforms defined? If so, you need to specify track_new_devices in the first device_tracker platform in your configuration.