Have you tried pressing in the earphones a bit harder than maybe you'd like? Sometimes, you think they are well seated, but they are not.
Give that a try and see if that helps (cause the headphones that came with my Nano ... and my iPhone ... work fine).
Marilyn