There shouldn't be a problem finding the staff first, AFAIK, but that may have been what got messed up somehow.

Did you go back to Cecil and tell him you had the staff? You would need to do so with the character that has it in their inventory.