A couple of years ago Verizon essentially halted all new fiber roll-outs -- nationwide.

http://online.wsj.com/news/articles/SB1000142405270230341040...

They are still wrapping up the details on a couple of long-term rollouts, but they decided they would rather spend their money on the more lucrative wireless oligopoly. They did manage to get the DoJ to sign off on a deal to collude with comcast so as not to poach each other's customers.

http://stopthecap.com/2012/08/16/settlement-over-verizon-cab...

So there may well have been regulatory hurdles in your case, but Verizon pussing out (with a new CEO) is the reason you will never get FIOS.