After all different tries with different solutions...This now works for me:
Step#1: Clear registered devices:
Open iTunes
-> click on "store" in the upper left corner
-> from the drop-down menu, select "view account"
-> enter your password
-> under "iTunes in the Cloud", click on the blue "Manage Devices >"
-> remove any old devices
Step#2:
a)Make sure your device has USB connected to the device but not to the computer
b)Turn device off
c)Do the two steps ON THE SAME TIME: 1) hold home button down (don't release) 2) plug the cable to the computer
d)When you see the cable and itunes icons on your device, release you hand from the Home button
e) in iTunes application, click on restore and follow the wizard