Automatically generated according to the speed travelled on by each users of the system. Can change along one street. Not sure how you would cope with people who speed and that.
Street Names and Point of Interest
Entered by users. When a map is downloaded and used by another user they can agree with or modify the name of a POI or a Street Name. You would need to introduce something of the concept of 'trust'. The more accurate someone is at entering 'data' the more their entries 'count'.
This would weed out people screwing with the system.