Normally I can help with any new nano problems since I have one and have had my fair share of problems but I've never had that happen before. I would email apple or take it into an apple store.
Things on the top of my head that it could be...
R u hitting the middle volume button that pauses the music (I do this a lot)
R u running and have shake to shuffle turned on but there isn't another song to play so it stops
Other than that I'm not sure.
Is it every time? Or just sometimes? Is it every song?
Is it possibly your headphones?