(Debugging was already on, USB cable plugged in, fresh restart)
SOLUTION:
Switched USB connection from Media Device (MTP) to Camera (PTP).
When I did this it the PC installed device drivers, then phone gave me my computer's fingerprint and had a dialog concerning allow device to use USB Debugging. Accept. Device shows up in eclipse. All good.
(On Samsung Note II API 19)
Note: it's good habit to always try toggling the USB mode. I don't think it's the act of designating Camera (PTP), but the dialogs that are generated when doing so. Also, I had my phone replaced: I remember seeing this dialog before but not on this phone. Maybe there's an option somewhere to enable it per device?