Determine if items can be ordered grouping two simultaneous criteria
There is a $O(n)$ time algorithm for your problem, using standard graph algorithms.  You basically reduce it to connected components decomposition, which can be done in linear time.

Build an undirected (multi-)graph, where we have one vertex for each letter in the input.  For each pair of items that share the same number, say Xi and Yi, add an undirected edge between X and Y.  This might introduce repeated edges.  That's ok.  Leave them as is; don't collapse them down to a single edge.

Once you have this graph, your items can be ordered if and only if every connected component of this graph is a simple path.  You can test this condition by decomposing into connected components using standard algorithms, then for each connected component, checking that no vertex has degree $\ge 3$ and that either (i) the component consists of only a single vertex, or (b) there exist exactly two vertices in the component with degree 1.  The whole thing can be done in linear time.



The idea here is that we're trying to find an ordering of the letters (the vertices), subject to some constraints: each edge (X,Y) represents a constraint that the letter X has to be adjacent to Y in the final ordering of letters.  The graph I defined above encodes exactly the constraints that apply, if we want to find an ordering of the items.  Notice that there exists a valid ordering of the items if and only if there exists a valid ordering of the letters that respects the edge-constraints: given an ordering of the letters, each letter represents the group of items containing that letter, and you can easily arrange what order to put the numbers in.

The key insight here is to build a graph with one vertex per letter rather than one vertex per item.  Once you do that, everything falls out more or less straightforwardly.

Credits: I thank Raphael for a crucial idea that helped me find this,  AlexDev for pointing out some subtleties that helped me work out the details, and reinierpost, whose answer helped me realize a few other tricky details.

By the way, you might notice that my solution ends up looking very similar to reinierpost's elegant algorithm.  Indeed, when the graph is connected, my solution is equivalent to his algorithm: his y[A] is just the degree of the vertex A in the graph I defined.  The difference comes when the graph is not connected; my algorithm handles that case correctly, but I think his algorithm gets a few corner cases wrong.  Nonetheless, the ideas are extremely similar -- and I hope my exposition helps understand the ideas behind his elegant algorithm.



This algorithm also generalizes to the case where you have more than two attributes.  For instance, suppose each item has a letter, a number, and a color.  Start by forming a graph with a vertex per letter and an edge (X,Y) whenever there are two items that share an attribute and whose letters are X,Y respectively; use the same techniques to look for a valid ordering of the letters.  Then, for each letter, you need to look for a valid ordering of the items containing that letter.  This can be done by a recursive call.  There is a slight twist, in that during recursive calls you might have an additional constraint indicating which item the sequence must start and/or end at, but it's easy to adjust the algorithm to take this into account.  In this way you get an algorithm whose running time is $O(kn)$, where $n$ is the number of items and $k$ the number of attributes.