I just received the new iPod nano (6th gen) today and along with I got a spotify gift card... When I went to connect my iPod to Spotify it simply would not connect. I know I can connect nanos with spotify because I have done it before.
I have restored and updated the iPod.
Made sure Spotify was up to date.
Spotify Version: o.8.5.1333.g822e0de8
Mac OS X 10.7.5
iPod Version 6g 1.0.2