I think I had to do a restart after inserting the SIM card. After some issues getting my gmail account to sync, I tried placing a phone call to get redirected to Verizon's activation line. Everything went smoothly once I did that.
My wife bought the Nexus for me last week when it came out. The store let her walk out and said I could activate it with the instructions they provided. It didn't work, so I called tech support and gave them the sim card number and other information from the back of the phone, and it was activated in a couple of minutes. You need to call from another number, not the one you want to activate. It took like five minutes.