The size of roman towns is somewhat smaller than today, and since people generally had little else to do but gossip about other peoples business, anyone seeking an adress had only to ask around - someone would know where they lived, and a few directions from a landmark within the town would suffice. Rome was of course much larger but the same principle applies, and since that city contained 'ghettoes' of varying nationalities, its a fair bet there were sub-communities that keptt track of goings-on. Given the level of junk mail they received was nothing like today, I doubt the romans had much problem with street names, since major roads were sometimes named and used as landmarks in themselves.
I would very much consider Pompeii a minor city in the empire and yet, no mater how much time they ever had for gossip, I would not recommend trying to ask your way to someones house in a city of between 6.000-20.000, unless the person was very prominent.
If they had a problem with street names then? Probably not since we do not find very many names, but I think we should find other reasons then only gossip behind it.