I created a new tauren druid yesterday, and ran her to Silvermoon (that's all I did with her, save pick up a couple flight paths and greet some elders). Today when I logged in, I noticed that the keybinds weren't showing up. I ran a little test - key 3 is bound (blizz default) to "war stomp". So I hit key 3. STOMP!
So, per your request, Scott. I logged out, disabled all addons, and logged back in. The (default, I presumed, since I'd set no bindings in nUI at this point) keybinds showed up. Logged out, enabled nUI only, logged in. No binds. I also noticed that the "<ctrl-alt-rightclick> to set key binds" note did not appear in the tooltip. Hit <ctrl-alt-rightclick>, got the keybind window, bound slot 1 to key 1. Logged out, logged back in. All 3 binds now show up.
Changed the slot 1 bind to 4, just to see what would happen. Now after logging out and back in, "4" shows up on the button, and hitting 4 activates that ability. Hitting 1 (which is still the Blizz default) does nothing. Changing the bind back to 1, all the binds still show up, and 1 works for button 1 (4 no longer does anything).
I'm going to add a few addons to the list on this toon. I'll report back if that causes the keybind problem again.