I don't think you have to talk to anyone else first. I just started a game recently and when I saw your problem I went to Daggerfall (for the first time), talked only to Aubk-i, and got the normal Nulfaga quest. I've only been out of the starter dungeon 5 or 6 days and was lvl 4. The only requirement, as far as I know, is that you're level 3.
Yeah, I tried talking to her when I was out of the privateer's hold (obviously), but before I got the mysterious note. Spent the first two hours of the game trying to figure out why my compass was sideways and east was down.
Fixed that, found the castle, exhausted myself trying to talk to the queen, collapsed from exhaustion, got eaten by wild animals right inside the castle.
I LOVE this game.
I'm gonna double check whether I'm level 2 or 3 in a second.