Go back to the elementals and talk to them again. They only gave me the rune after I'd found the White Witch. The staff disappears after you free the Elementals, that's why you can't find it.