My Ipod Nano(5th Gen) is stuck at "Connect to Itunes to Restore"

I recently bought a used Ipod Nano from a local Tunes store (Along with an Iron Maiden vinal), and upon going home and connecting it, and formating it, I got "Please connect to Itunes to Restore" on an endless bootloop.

(The cable works fine, I tested it with an old 2 gig 2nd Gen nano)