Does the NCE decoder have back-EMF? If not, you may just have to adjust the "start" speed up to where the motor voltage finally starts to move the locomotive. I've got some Digitrax DZ-123's that are that way, and I've got start values of something like 120 (out of 255) on one or two.
If it DOES have back-EMF and the decoder is supposed to be actually reading motor speed, then I can't figure anything but a defective decoder. Even a binding drive train shouldn't just be completely inert up until 40% throttle is applied. The Back-EMF would ramp up the voltage until it got the motor spinning.
On a side note, I've been burned beyond recognition by Atlas' old Lenz decoders and they kept using those for YEARS. Unless and until Atlas can prove to me that they've changed their head-in-the-sand ways about their decoders there's no way I'd buy factory-installed from them. Just sayin'.