Cannot get MTP to work unless USB debugging is enabled
Do you have Samsung Kies installed? Samsung phones don't use the generic Google-provided driver for MTP in Windows, but if you install the correct Kies version it'll also load the relevant driver. This post on XDA-forums explains more about the cause, just don't forget to substitute the Samsung driver for the Google one when following the steps.

If you don't want to mess with Kies you can obtain just the Samsung driver portion here.