Yes. You cannot block a utilities right of access.  The fence should not have been put up without their consent.