Should the Deck Marker change more frequently?
As you say, from the rules:

Shuffle the deck of Encounter cards and place it to one side. Place
the morning marker next to the deck.  When  there  are  no  more
cards  in  the encounter deck, reshuffle the discards and re-use them.
Also, replace the morning marker with the noon  marker

If  you  reshuffle  a  second  time,  replace  the  noon  marker  with  the  night  marker
(If you need to use the deck a fourth time, leave  the night marker in place.)


There is nothing in the rules or FAQ that would enable you to go through the deck faster than one per turn. For a game that plays a wide range of players (2 to 6), that creates a wide range of rounds required to get through the deck. Combined with the many options in the story book, this could result in small groups not seeing significant parts of the stories over time. Which is what has been widely reported.
Suffice to say it requires some changes to make it work well, and there are a number of options, some suggested in the above links:

Divide the encounter deck into smaller decks each marked with the morning, noon, and night tokens, simply switching to each deck as you finish the previous one. This will work well for player counts where you do manage to get almost through, or through the deck at least once.
Start the game at a different phase, either by consensus, or randomisation. This is good for groups that play together frequently and want to experience the different stories over a longer period of time.
Change the phase at the start of each round (i.e. when you reach the starting player). Works for any player count, and can add more variety into the game. Story wise it allows everyone to play through a morning, noon and evening phase and can make a story of a thrilling day.
Switch phase with each player. Doesn't work with player counts of 3 or 6 as players will always have the same phase on their turns. Will work well for other player counts.
Randomise the phase for each player using the destiny die, utilising a pre-determined specification for the -, +, and blank results (e.g., - is morning, blank is noon, and + is evening)
Utilise predetermined triggers in destiny and story points to decide when to change the phase, e.g. when someone reaches 6 total points, go to noon, when someone reaches 13 total points switch to night. Could be a group wide change, or per player change.

And many, many more variations. Changing the phase doesn't seem to increase or decrease difficulty, so there's no reason to stick to the rules as written when they don't give the variety needed in a story telling game. As with all house rules, it's best that they are identified as house rules, be explained clearly, and all players agree to utilising them.
As the FAQ states:

The    Golden    Rule    of    Tales    of    the    Arabian    Nights    is,   &quot;Whatever    makes    for    the    most    entertaining    story,    makes    for    the    best    game.&quot;

So choose the option that give your group the most entertaining story, whether that be sticking to the rules, or implementing one of the variations above, or something else.