Also try this: launch iTunes with the Nano attached and then eject it from within iTunes. Press and hold the play/pause section of the clickwheel to turn off Nano. If it's working this will place it into a dedicated charging mode. Hopefully that will work for you.
You may also have a bad USB cable too.
If you can't get it working today, return it! If you got it at an Apple Store, I'd open your new exchange in-store for them to test and make sure everything is working.
Good luck.