Assuming you are playing the most recent version of the game, there should be an abandoned cave south of Eleen. You will need to finish some quests with the governor first, so make sure you talk to him.
I also ran into this problem. It would def be worth adding a bit to the end of the "kill vermin in the cave for gold" message to say something like "Maybe you should check with the governor?" at the end, would make it a lot more obvious what to do.
