ipod nano 7 bluetooth not working!

My brand new nano 7 bluetooth is stuck in "now discoverable - searching" but does not find my bluetooth headphones (Sneer - 801 with A2Dp profile - - should be compatible!)....I have tried reset, I have tried powering down and back up the headphones, and nothing is showing up; is this a hardware problem with the nano? Should I take it back? SO frustrating. The only reason I wanted the nano was to be able to use the wireless headphones while I work out/go running....