Is this an "iPod touch," as shown in your profile info, or a different type of iPod? It may be important to know the exact iPod model, for this problem. You can look at this list to help ID the model.
Also, do you use a Mac or Windows PC?
You can try this... Shut down (power off) your computer. With iPod NOT connected, start it up. Use this procedure to reset your iPod (use the steps for your iPod type)
Then, run iTunes. Connect iPod. Try doing a Restore again.