The plumber and homeowner where the work was performed are the ones who should pay the costs...HOWEVER, I'd just bitch to Verizon...tell them your service is out...and has been out for x days...and DEMAND they come fix your service. It's up to them to recoup the costs from the liable parties.
Actually reading the law that someone posted, it seems like VZ is the one who is liable as they did not bury the line properly, as a few inches is not deep enough.