Hmmm, according to this page, Cid should be at the following map co-ordinates in the Fogfens in Mor Dhona: X:14, Y:11 (it's the exact same spot he was when you had to speak to him to start the quest). It's possible you might have missed this spot, as it's a fair way away from the Castum and hidden down in the swampland. If Cid isn't there though, I have no idea how else this could be fixed I'm sorry to say.