Anyone know what the max level required to open constellation story? It has been 2 years already and I am at level 56 with no story access. That is insane.

You have to reach lvl100 just on one to unlock the story.

Your level is low. You need to do the main quest continously until you reach the Constellation Story.
Constellation quest is most likely after Desert main quest so you gotta check your quest status from the Menu - lower left side (Content) to see the list of main quest.