I experienced identity theft with Verizon, too. Way back in 2000. It was taken care of almost immediately with a single phone call. I had to mail in some proof of identity (photocopy of my water bill, IIRC) to verify that I did not in fact live in whatever place the account had been opened and that was that.

I get the sense that a lot of things that used to be easy to resolve, easy to deal with, easy in general, are actually quite painful and difficult today.