I got it working. What I did was Restore>Setup as New Phone>then follow the directions posted on page 4.
How far did you go with the set up as new phone? Did you go until the phone said could not set up new phone and then itunes asked to restore from backup, but didnt restore? Or did you actually set it up as a new phone all the way?
When I restored last time, the situation above happened where i got an error in setting up new phone