In Russian, нужен/нужно/нужна/нужны take the dative. The person needing something is put in the dative case. So им был нужен is quite clear and means "they needed". Now, the sentence:
Кто им был нужен
means "Who did they need"? "Who was necessary for them"? I would have expected that кто has to be put into the accusative, i.e. кого. In German, for instance, when I ask this, I would ask "Wen oder was brauchten Sie"? and it's cleary accusative. Not nominative.
Same holds for other examples, like Мне нужна ваша машина. Why not Мне нужна вашу машину*?*