Do the bands of a photonic crystal (or semiconductor) ever cross? If not, why not? If so, is there any special physical phenomenon that occurs at the crossing? And...if two bands cross, how do you reconcile which band is which after they cross?
Yes, for example in a Dirac (2 dimensional space) or a Weyl (3D space) point. There is a vast amount of research on these peculiarities of electronic and photonic bands in the context of topology.
I am not sure about your question (Phonons? Electrons? Photons?). The bands typically represent energies in the K-space (i.e. they are a four-dimensional entity), those states( energies) are discrete (bands) when assuming periodicity of the lattice etc. Thinking on phonons in a semiconductor the bands represent the Energy-Momentum of the different modes in the lattice (optical, acoustical, longitudinal transversal, shear etc...). When represented on a 2D plot those bands can cross with the crossing representing a degenerate state (for that point in the K-space there are no longer 2 separate bands/modes but only 1 mode). For photons and electrons, this interpretation is a little bit different (see the avoided crossing phenomenon: https://en.wikipedia.org/wiki/Avoided_crossing //// http://condensedconcepts.blogspot.co.uk/2016/09/a-basic-quantum-concept-energy-level.html). In general yes, you can have degenerate points where bands merge in one point of the K-space (Dirac and Weyl points) and quite interesting behaviours arise on those points (electron behaviour in graphene for instance).
In addition to agreeing with the above, I would like to offer the following observations:
Complex structures may support multiple modes, which may or may not be orthogonal to each other. Based on my observations, modes which are not orthogonal will couple in the vicinity of their intersection, resulting in some sort of distortion of both bands (level splitting/bandgap phenomena); or they will be orthogonal and not couple, in which case they will simply cross each other without effect.