In The Original Series, and subsequent series, it was established that cloaks weren't perfect, especially Klingon ones. In "Balance of Terror", the Enterprise could detect the Romulan ship moving when it was under cloak, but not closely enough to target it, only enough to get a sense of what direction it was and its course (since the episode was essentially an adaptation of "The Enemy Below", the similarity to WW2 submarine warfare isn't coincidental). "The Enterprise Incident" was about Kirk and company stealing a new version of the cloak that allowed for it to move undetected, at least at relatively slow speeds. In later series, there were a few episodes that established that if Klingon ships went to too high a warp speed, they could be detected even with the cloak on.
So the easy explanation is that this early version of the cloak works, but only at sublight, or perhaps very slow warp. At warp speed, ships can be detected even under cloak, but as soon as they drop out of warp, they essentially vanish. At warp speed they can be tracked and even identified by comparing the warp signature to what's in the records.
Going back to the submarine warfare analogy, consider the ship under cloak to be similar to a submarine moving at high speed: when it's moving fast, a sub, even a modern one, can make a lot of noise which allows for it to be tracked fairly easily over long distances and can provide enough acoustic information to identify at least its class. (There used to be an old joke that when an Alfa put the pedal to the metal in the Barents Sea, you could hear it in Bermuda). Once it slows or stops moving, however, it's a great deal harder to find and track.
Thus, again, the easiest explanation is that Starfleet can detect ships under cloak when they're moving at warp, but once they drop to impulse, the best they can do is "There has to be a Klingon ship around here somewhere because we detected it arriving."
