The saga continues... So I took the car in to replace the old (8 days old) part with the new one. Then I got a call, expecting for them to tell me the new part has been registered with Nissan and I can pick up the car. Instead they told me they put in the new part, but when they tried to register it with Nissan, they couldn't. Somehow Nissan NA wasn't able to recognize that part. So it's still not working. I'm leaving the car overnight hoping they can get it handled before I need it tomorrow. If they can't, I'll have to pick up the car as is and either give up and get a refund, or bring it in a 4th time.
Bottom line: I suggest waiting to get this done until your dealer has done a few of them successfully under the new protocol and new parts.
Edit 12/7: the dealer called me this morning and told me that Nissan (Tenn.) sent them an email saying it can take up to a week to register these new 3G devices. The dealer couldn't tell me whether it would spontaneously start working after a week or so, or whether I might have to bring it back in at that time. This sounds like a sitcom story arc or maybe comic strip. It would be funny if it were happening to someone else.