I was looking for an easy mechanism to record new routes in to Google Maps. I think I found a one. My Tracks for Android. http://mytracks.appspot.com/
This can be downloaded from Android Marketplace. Search for "mytracks". When you have taken a route which is not on Google Maps the application can be used to record the route you are travelling. Then it can be published via Google My Maps.