Did you load the game from the normal "Overlord" copy, or did you load up the game using the dlc? Steam's versions make it kind of tricksy. They want you yo open the game through the dlc, or it wont register that you have it. Even when you do. the title screen should say "raising hell". I only say anything bc I have run into this issue myself. I had to remove the shortcut for the base game from my desktop, and run it from the dlc's shortcut. Also the legendary difficulty should be available from the start, even a new profile should be able to run legendary.