Power of All on illegal target

Good afternoon,
yesterday during a tournament final, the judge in charge had to make a difficult decision we're not still sure it's the proper to take.

Luckily we've the registration of it, i will paste at the proper moment:

LINK

The Malkavias is bleeding with sleeping mind, +1 stealth. Blocks are declined, then he plays conditioning superior.
After some seconds, the banu haquim decides to deflect with telepathic misdirection, redirecting the bleed on the bottom-right player in the video.
Only in that moment, that player decides to play power of all in order to cancel the conditioning.

Judge decided that the target is illegal, because another card was played in the meanwhile so it can't be canceled "as it is played", and let Marco to draw back the card, without replacement.
My interpretation would've been that the card was played, and since he declared an invalid target, should've make another declaration on a valid target (like you do in the case you declare a metuselah with less pool than you in a parity shift referendum, for example)

Which interpretation is correct? Why? And which part of the rulebook describes so?

Thanks in advance for the reply