The gemara[1] indeed states that the kohanim should not turn around until the chazan begins Sim Shalom. Therefore, it seems that you should have waited until he actually started Sim Shalom, as an introductory tune does not have halachic standing. However, the matter deserves a better look.
Rashi[2] describes the end of Birkat Kohanim as follows: The congregation finishes saying amen to the last beracha, the kohanim turn around and close their hands, the chazan starts Sim Shalom, and the kohanim begin reciting “Ribono shel olam…”[3] This sequence places turning around after amen but before Sim Shalom, such that in the case you describe, you would not have had to wait.
How could Rashi contradict an apparently explicit gemara? The Maharshal,[4] based on Rashi, explains that the gemara means that the kohanim wait until the appropriate time for Sim Shalom has come – that is, when the congregation has completed answering amen.
While Tosafot[5] and the Ran[6] quote Rashi without comment, the Rambam[7] and the Shulchan Aruch[8] describe the halacha according to the simple reading of the gemara – that the kohanim wait until the chazan starts Sim Shalom. There is no indication in their wording or in the sources that the Beit Yosef and commentaries cite that they accept the somewhat novel approach of Rashi/Maharshal to the gemara.
Let us see if there is any halachic reason to have to wait literally for the beginning of Sim Shalom even when its recital is unusually delayed. The apparent logic for the kohanim not to turn around immediately is that they should not rush to finish their job before Birkat Kohanim is totally finished, perhaps thereby showing disrespect to the blessings and the blessed.[9] If so, this logic might also dictate that beginning Sim Shalom is not necessary, as long as Birkat Kohanim is over.
Alternatively, we could explain that in general, one must begin the subsequent beracha in order to conclude the previous section, which in this case is Birkat Kohanim. This point seems to find support in a similar concept that we find in another halachic discussion. If, during the winter, one did not mention the phrase about rain in the second beracha of Shemoneh Esrei and did not realize this until after he completed that beracha, he must return to the beginning of Shemoneh Esrei.[10] However, the Shulchan Aruch[11] writes that the beracha is not considered over in this regard until one begins the next beracha; before then, he can insert the mention of rain at the point he is up to when he realizes his omission. This provides a precedent that the end of one section (e.g., Birkat Kohanim) depends on the beginning of the next (e.g., Sim Shalom). Accordingly, it would be necessary to actually start Sim Shalom and not just be ready to do so.
There are also strong indications[12] that Sim Shalom is the natural continuation of Birkat Kohanim and may serve as a confirmation of the blessing.[13] This makes it the appropriate time for the kohanim to commence the second stage of their blessing by saying “Ribbono shel olam…”[14] Therefore, it makes sense to argue that the gemara means that the kohanim should turn around and say “Ribbono shel olam” only after Sim Shalom has actually begun.
Thus, kohanim should ideally follow the consensus of poskim[15] and refrain from turning around until Sim Shalom has begun. Chazanim should not procrastinate or chant before Sim Shalom, as that confuses the kohanim and the congregation.