Relay takes time to close
Assuming your supply isn't collapsing somehow, to me it's most likely that the CTR of the opto isn't sufficient to saturate Q1 and meet the pull-in voltage requirement of the relay:


The typical forward drop of an optoisolator photodiode is on the order of 1.5V
There's another LED in series with the path, dropping at least another 0.7V


The photodiode current is going to be on the order of:

\$I_D = \dfrac{5V - 1.5V - 0.7V}{1k\Omega} = 2.8mA\$

The vast majority of optoisolators that I know of only guarantee their CTR at 5mA current or higher. Even a high gain opto (100-300% CTR) will underperform at this current level. It's quite possible that many optos in this application will tend towards higher CTR and work without circuit modification. Also, some Q1s may have much higher \$H_{FE}\$ and handle the weak drive.

I would consider soldering another 1k in parallel with the existing R1 and see if the relay performance improves. Most optoisolators can handle up to 50mA photodiode current; that being said, the diode current should be set to the lowest possible current that allows your application to operate robustly, since optoisolators do age (the CTR degrades over time: faster as the photodiode current increases).