To open Johnny's Shop in Esthar you just have to try over and over again until it opens. It usually takes me around 20 tries. When you have opened it once, though, you can access it at any time through GF Tonberry's Call Shop ability—if you have it—where it will show up as "Esthar Shop!!!".