No reason to start a new character. If you want to level a new class, and assuming that class is still low level, you can do all the new lower level content with that class. I've never done much FATEs, so I really don't know much about that, but doing dungeons is quite a nice way to level alongside some quests and the occasional FATE if you happen to run into one. Variation makes the levelling process a lot more fun