  Using numerical simulations we show that a variety of novel colloidal
crystalline states and multi-step melting phenomena occur on square and
triangular two-dimensional periodic substrates. At half-integer fillings
different kinds of frustration effects can be realized. A two-step melting
transition can occur in which individual colloidal molecules initially rotate,
destroying the overall orientational order, followed by the onset of interwell
colloidal hopping, in good agreement with recent experiments.
