I bought this game on Steam recently, and I am having the exact same problem. I talked to the sailor very early in the game, perhaps even the first time I went to Arcadia. Now it is the second trip there, and I have won the cups game and asked to trade the screwdriver for the bird, but she just keeps on saying "I haven't decided yet".

Did you solve this?