Uncaught InvalidValueError: not a Feature or FeatureCollection

I had the same problem (or at least similar) and solved it by introducing one extra step.

Origin of the data: My semantic Network delivers on a first round request the data about the caves in Southern France in GeoJSON format. This is directly imported via:

map.data.loadGeoJson(theUrl);

As we might want to work independent of the semantic network with these data (the app is a thick client) the caves are locally stored via jStorage. Iterating of the features of the map and storing these objects directly in jStorage failed because of circular references. I made a handcrafted routine (not generic enough but suiting the purpose) to transform the map.data.Feature into a javascript object that could be stored.

When getting the data from the store:

var cave =  $.jStorage.get(key);
map.data.addGeoJson(cave); 

throws the Uncaught InvalidValueError: not a Feature or FeatureCollection error.

But:

var geojson = JSON.parse(cave);
map.data.addGeoJson(geojson);

Works fine.

My interpretation is that the function addGeoJson needs a javascript object and not a string.

Sample geoJson (the orignal "cave") value:

{ "type": "Feature", "geometry": {"type": "Point", "coordinates": [5.368743302306143, 44.0421921072459]},"id": "84.MON.014", "properties": {"nom": "Aven du Grand Guérin", "nid": "7b4703-f387f6f544-0750e59f441be7bb30a7e097c5d725f7", "nature": "Aven", "nodeTime": 1400743203325, "dataId": "5b66137c-1461fdfe5ca-f528764d624db129b32c21fbca0cb8d6", "status": 1}} 

The specification for GeoJSON can be found at http://geojson.org/geojson-spec.html Relevant (though experimental) Google Maps API documentation can be found at https://developers.google.com/maps/documentation/javascript/3.exp/reference#Data

So it looks like for GeoJSON to be acceptable by Google Maps, you need to wrap a Polygon (or similar) returned by MapIt in a Feature or FeatureCollection, here's an example for bermuda-triangle:

  { "type": "FeatureCollection",
    "features": [
      { "type": "Feature",
         "geometry": {
           "type": "Polygon",
           "coordinates": 
              [
                [
                  [-80.190262,25.774252],
                  [-66.118292,18.466465],
                  [-64.75737,32.321384],
                  [-80.190262,25.774252]
                ]
              ]
         }
      }
    ]
  }

for the data provided by http://mapit.mysociety.org/area/11804.html it has to be:

  { "type": "FeatureCollection",
    "features": [
      { "type": "Feature",
         "geometry": /** paste here the complete output of 
                         http://mapit.mysociety.org/area/11804.geojson **/
      }
    ]
  }