Had this a few months back when I did a complete rewire on a neighbor's house. The guy doing the plastering came along and had to temporarily remove one of my 3-ways, then he put it back with the common and one traveler swapped over. The circuit had a 4-way in it as well, and he tried to convince my neighbor that you couldn't have it wired so that all three switches could turn on the light no matter what the position of the other two switches.
You should've seen the look on his face when I swapped out the two wires and it all worked as intended.
The only thing that crossing the two travelers does is affect which way the switches have to be for on/off, e.g. whether both switches the same way=on and one up, one down=off or vice versa.
I've found that some people are quite picky about this! Do you always try to wire so that both switches down=off, or do you just connect the travelers randomly?