In many parts of the world, OSM data are better than or competitive with google data. Especially impressive for this application is the collection of foot and bicycle paths in the database. I think that Mapquest has APIs that would be suitable for use on this site (http://developer.mapquest.com/web/products/open). It would be awesome if we could route with those data and folks using this awesome site would be encourage to make OSM better!
OSM-based routing would be really nice.
CloudMade has a routing API for this, which is used by bikehike.co.uk. Maybe it could be integrated into gmap-pedometer, too?
As pointed out by pigah, OSM has many interesting paths for runners that google maps doesn't know about.
After every training i correct osm data. It would be great to use those paths to measure my route on these paths.