I hop off the phone and go online and do so.. but it took a few days and another phone call to the DMV get it done. When you update the car’s registered address, you have to include not only the license plate number and VIN, but also the “Effective of” date of your current registration. Since I had paid my renewal in April and we were now past my renewal date of May 20th, it was now in the system as a given day sometime in May 2016, not the 2015 on my old paperwork that I was mistakenly referencing. I didn’t think about that at first and it wasn’t until i began to randomly try various dates in a week long window around the date stamp on my email receipt for my renewal that I finally got it to accept the update submission.
I then decided to wait a week or two, because lord knows government systems are probably slow to share info among themselves… and call back in today. After putting my number in the queue and getting a call back, I explain my situation to someone and ask to have the sticker resent to me. He asks for my my address again, which I give. I’m then asked for a possible previous address I may have had… oh boy.. here we go. I give my previous address, but I’m told that’s not on file either. I then offer up my address before THAT, my first one in LA and where I lived when I bought the car in 2014. He says THAT is the one on file.
Flabbergasted, I ask how this can be. I updated my contact info when I moved in Nov 2014, and again in Feb 2016. Clearly it worked because my ID contact info was mailed to the right place! He informs me that online updates do not work for leased vehicles. What?!? I ask why is it the system behaves as though it works then, and why it does not give me any error telling me this.. (also for the record, you online profile for the CA DMV does not reference your address to verify what’s on file. This is by design, I’ve been told.)

Seriously… I did everything they told me to do in the way in which they told me to do it (proactively I might add!) and now I have to pay a fee for a second copy because *they* gave me bad instructions.
In 2016, I can’t believe dealing with the DMV is still this convoluted and archaic. The only relief is the fact that my registration IS up to date, I just don’t have the piece of paper to go in my car and a shiny new sticker to go with it.
UPDATE! @ 4:50pm 6/9/16
Whomever said complaining about something on twitter doesn’t fix it clearly underestimates the CA DMV!
@sargonas We would like to assist you. Please email your contact info to us at [email protected]
— CA DMV (@CA_DMV) June 9, 2016
So I emailed the address in question with my email and phone number. Just now, about 15 minutes ago, and *exceptionally* nice lady called me and asked to hear my story. I ran her through the whole shebang, and she was super apologetic and asked if I would be willing to fill out the PDF of the change of address form and email it to her. Once I did, she would process it within the next business day and have the new registration in my mailbox within the next 7 business days.
Wow! The CA DMV is NOT whom I expected this kind of personal touch from! The systems and processes may still be a little convoluted and janky, but at least there’s a light at the end of the tunnel!