I've noticed this suspicious behavior of "cube" data type with ORDER BY, which I believe is a bug in the extension (or the GiST index support). The following example comes directly from regression tests added by 33bd250f (so CC Teodor and Stas, who are mentioned in the commit).
This query should produce results with ordering "ascending by 2nd coordinate or upper right corner". To make it clear, I've added the "c~>4" expression to the query, otherwise it's right from the test.