Propozycję zaakceptował już zespół ds. nazewnictwa krakowskiego magistratu. Teraz przed pomysłodawcami najtrudniejsze zadanie – należy wybrać ulicę. Problem w tym, że w centrum Krakowa wszystkie ulice mają już swoje nazwy; imieniem Marka Grechuty można by nazwać właśnie budowany duży węzeł komunikacyjny lub czteropasmówkę łączącą północ z południem Krakowa. Tych atrakcyjnych ulic i placów w mieście jest jednak bardzo mało, a w kolejce czekają także tacy patroni, jak Lem, Kaczmarski, Kennedy, de Gaulle i Beethoven.
Zgodnie z literą prawa najwcześniej po dwóch latach od śmierci można nazwać ulicę imieniem zmarłego. Są jednak wyjątki. Dotyczą one laureatów Nagrody Nobla i honorowych obywateli Krakowa.
