Map matching is a key part of many GIS applications, linking observed GPS traces to road networks via a map, and allowing inference both of more accurate trajectories and of properties of the road network. But when the map contains errors such as missing or mislabeled roads, map matching can give poor or even misleading results. We show how existing map matching algorithms can be extended to make them robust to map errors and omissions, and discuss how such algorithms can be used to identify map problems such as missing roads, unmapped drivable areas (e.g. parking lots) and mis-directed one way streets.