The current "official" Apple USB power adapter is this one.
Older Apple USB power adapters that are white and square, as well as adapters made for larger devices (such as iPhone and iPad) should also work with a nano. The direct USB 2.0 port of a computer should provide enough power for a nano. It that power adapter is a third-party product (no matter where you got it), it is possible that it does not supply enough power. Even if it's an Apple power adapter, it may be defective.
If it charges properly from your USB port on computer, it is likely that there is nothing wrong with your iPod. Maybe you can go back to that store (with your nano and the adapter you bought there) and ask if you can try charging from one of the power adapters they have for their display models. If it works, tell them the one you bought from them seems to be defective.