The Cuckoo was a parasitic dream which existed in, and eventually took over, Barbie's dream world. It wished to one day escape, and create more like itself in other people's dreams, even if it meant destroying the dream world and everyone in it. The Cuckoo took the form of Barbie as a young girl, and enlisted one of her childhood toys as a spy.
The Cuckoo was able to send out agents into the waking world, and while Barbie didn't know the children of the Cuckoo, they knew all about her. This caught the attention of Thessaly, a witch who had no objection to entering Barbie's dreams to try and destroy the Cuckoo.
The Cuckoo, meanwhile, captured Barbie in the Dreaming, and told her that her dreams of the Land were nothing more than delusions of self-importance, and that she had trapped the Cuckoo in the Land by dreaming about it.
Utterly dispirited by the Cuckoo, Barbie agreed to help destroy the dream. The Cuckoo led Barbie to the Hierogram, a large monolith at the coast, which Barbie struck with the Porpentine. The Hierogram shattered and Dream appeared, and he began to unmake the Land.
Thessaly demanded the right to kill the Cuckoo for its threats, but it successfully escaped from Barbie's world, at which point it transformed into a black-feathered bird.