PLL is a control loop that operates on PHASE. There are lots of components to a locking time, but assume a simple example: the loop starts locked, and a sudden phase step happens. So a square pulse shapped error in phase happens.
Imagine now a corollary--if you tried to pass a voltage square wave thru a lowpass filter and see the output on an oscilloscope, and the filter bandwidth was too small, you would have to slow down the repetition rate of the square wave for the square wave output of the filter to ever settle. If you have too fast of a square wave input and it is not getting thru the lowpass filter...you could open up the bandwidth of the lowpass filter to see the output. A standard rule of thumb is, if your square wave had 1 uS on, and 1 uS off, you would want a lowpass filter at least 2.2 MHz in bandwidth.
The same happens in the PLL...since you have a step input to the control loop, you need the control loop bandwidth to be wide enough to respond in a reasonable time period.
(of course, if you make a big enough perturbation to a PLL, the system does not stay linear during re-lock, and all bets are off)