I want to point out that according to the wikipedia article on labyrinths this is a modern distinction by enthusiasts! Apparently, both in the traditional Greek and lexical English the words Maze and Labyrinth are synonymous. In any case, it is hard to guess whether either of them applies better to GRRM's (or the publishers) reading of the word. (https://en.wikipedia.org/wiki/Labyrinth)The difference between a "labyrinth" and a "maze" is that a labyrinth tends to consist of one intricate and winding path, but with no dead ends, whereas the maze consists of a number of paths, many of them ending in dead ends.
Personally, I've never interpreted "labyrinthine" as denoting a literal labyrinth/ maze that is built in stone, rather, like Howy said, meaning a confusing, asymmetric, chaotic interior with the ability to make one lose their way. I can imagine that GRRM did make that choice of words deliberatly as to avoid literal readings, but this is speculation.
Edit: Some canon quotes to help us along:
"Even more enigmatic to scholars and historians is the great square fortress of black stone that dominates that isle. For most of recorded history, this monumental edifice has served as the foundation and lowest level of the Hightower, yet we know for a certainty that it predates the upper levels of the tower by thousands of years.
Who built it? When? Why? Most maesters accept the common wisdom that declares it to be of Valyrian construction, for its massive walls and labyrinthine interiors are all of solid rock, with no hint of joins or mortar, no chisel marks of any kind, a type of construction that is seen elsewhere, most notably in the dragonroads of the Freehold of Valyria, and the Black Walls that protect the heart of Old Volantis. The dragonlords of Valryia, as is well-known, possessed the art of turning stone to liquid with dragonflame, shaping it as they would, then fusing it harder than iron, steel, or granite." - AWOIAF
"An even more fanciful possibility was put forth a century ago by Maester Theron. Born a bastard on the Iron Islands, Theron noted a certain likeness between the black stone of the ancient fortress and that of the Seastone Chair, the high seat of House Greyjoy of Pyke, whose origins are similarly ancient and mysterious. Theron's rather inchoate manuscript Strange Stone postulates that both fortress and seat might be the work of a queer, misshapen race of half men sired by creatures of the salt seas upon human women. These Deep Ones, as he names them, are the seed from which our legends of merlings have grown, he argues, whilst their terrible fathers are the truth behind the Drowned God of the ironborn. The lavish, detailed, and somewhat disturbing illustrations included in Strange Stone make this rare volume fascinating to peruse, but the text is impenetrable in parts; Maester Theron had a gift for drawing but little skill with words. In any case, his thesis has no factual basis and may safely be dismissed. And thus we find ourselves back whence we began, forced to concede that the beginnings of Oldtown, Battle Isle, and its fortress must forever remain a mystery to us." - AWOIAF
Last edited: