How to enable USB debug on Note 2?
I had to download Samsung's USB drivers for this device from their support page.

After you have the driver installed, when you plug in the device, Windows search windows.com for updates and finds:

Samsung mobile usb composite device
Samsung-sgh-i317
Samsung mobile usb modem
Samsung Android ADB Interface


Now, the interface still shows the "Connected as a media device" message, but adb devices list can see it.