I'd say 4000 odd pages in to the story is pretty late. I'm no writer, but I do know what I like reading, and I did not like this introduction. It's a new, supposedly pretty powerful player getting introduced, and I have absolutely no emotional attachment to them. I literally don't care about this character, I care about the other characters I've spent the last 4000 pages reading about, that I have an attachment to.
That's because the characters being introduced are bad, not because they are introduced too "late" into the story.
"It's a new, supposedly pretty powerful player getting introduced" pretty much describes almost all the new POVs from Feast onwards. Characters from the Dornish faction, the Aegon faction characters, the new Ironborn characters like Euron and Victorian.
It's quite clear that GRRM intended for the story to have different major acts. The first 3 books covered the first act of the story. Leaving many characters dead and entire factions fractured. Then he introduces a bunch of new elements in second act to expand the setting and give context to things which were mentioned in passing before. This is really not unusual in narrative techniques.
Again, the reason why people are so bothered is likely because a) the entire Aegon plot is an obvious distraction that is meant to create chaos but is not remotely a credible threat to the dynamics in the long term, b) because GRRM released two bridging novels and will never release another book in the series again, making fans frustrated that he wasted a decade plotting this shit instead of giving people the meat of the story they actually want to read.