JSON does not work
The API does not appear to be honoring the format parameter when json or jsonp is requested.
For instance, this query returns a XML document:
http://data.fcc.gov/api/license-view/basicSearch/getLicenses?searchValue=Verizon%20Wireless&format=json

-
Jared commented
Are you using a browser to look at the results? As far as I can tell the default response type is JSONP.. if you're using a webkit browser it will automatically parse this response in to XML, but if you curl the url or read it programmatically you will see the JSONP.
Still doesn't solve the issue though; it doesn't appear that the other formats work.