If you read the conditions in the document, they further define (b)(1) to be about interference with network operations or what not. The device should be FCC certified which means there should be a plethora of documentation that covers whether it would interfere with the network or not. This shouldn't take them longer than a week to check.
(c) Technical standards. For purposes of paragraph (b)(1) of this
section:
(1) Standards shall include technical requirements reasonably necessary
for third parties to access a licensee's network via devices or
applications without causing objectionable interference to other
spectrum users or jeopardizing network security. The potential for
excessive bandwidth demand alone shall not constitute grounds for
denying, limiting or restricting access to the network.
(2) To the extent a licensee relies on standards established by an
independent standards-setting body which is open to participation by
representatives of service providers, equipment manufacturers,
application developers, consumer organizations, and other interested
parties, the standards will carry a presumption of reasonableness.
(3) A licensee shall publish its technical standards, which shall be
non-proprietary, no later than the time at which it makes such
standards available to any preferred vendors, so that the standards are
readily available to customers, equipment manufacturers, application
developers, and other parties interested in using or developing
products for use on a licensee's networks.
And the legality is not really debatable, its clearly outlined that the burden of proof is on Verizon:
(f) Burden of proof. Once a complainant sets forth a prima facie case
that the C Block licensee has refused to attach a device or application
in violation of the requirements adopted in this section, the licensee
shall have the burden of proof to demonstrate that it has adopted
reasonable network standards and reasonably applied those standards in
the complainant's case. Where the licensee bases its network
restrictions on industry-wide consensus standards, such restrictions
would be presumed reasonable.
If you're a new customer (i.e., don't already have a SIM) wanting to get a Nexus 7 on to their network, they are effectively 'refusing' to attach the device.
