i would skip the step and just sync contacts and all data from Google. i find that most backup app "restores" can be flaky and i only use them to restore in emergency situations. a clean sync direct from the source ie Google is always best IMO.
good luck.
Make sure your phone is activated on your Verizon account