Samsung devices have begun to include a feature called 'Auto-Blocker' that prevents USB Debugging turned on. This feature can be bypassed by doing the following:

On the device:

1. Go to Settings > Security and Privacy

2. Scroll down to "Auto Blocker" and change the toggle to "Disable"

3. Click "Turn off" on the pop-up.