I've just tried scrying and talking to Eolus again, but the mine is the same. I'm definitely in the right place too - the entrance glows red when I hover the cursor over it, but it is simply blocked by rubble.
The king never actually said anything about the mines, he just rants about elves, but I only talked to him after I had received the council quest.
I'm going to give hex editing a try - if I have trouble with it, I will let you know.
