I didn't have any problem. Playing a warrior, I reached level 15 entering Maxos' temple, and almost got to 16 by the end. In general I try to put off any main plot quests as long as possible, and explore everywhere and do side quests first.