"Pod klonami" rzeczywiście brzmi brzydko. Can you maybe replant the street with another tree? I like "Pod kasztanami"!

The formula "Pod X (usually pl.)" is often used for restaurants/bars/clubs, as in "Under the Sign of X". See the famous cabaret "Piwnica Pod Baranami (http://en.wikipedia.org/wiki/Piwnica_pod_Baranami)", or Czesław Niemen's jazzy "Pod Papugami (http://www.youtube.com/watch?v=fAyCgWhYuCg)".