NP-hardness on Cayley graphs
Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley graphs. For instance, shortest paths on circulant graphs (a special case of Cayley graphs) are NP-complete; see "On Routing in Circulant Graphs", Cai et al, COCOON 1999, doi:10.1007/3-540-48686-0_36

Of course that doesn't apply to the exact statement of the problem you give (where the group is given as a multiplication table, itself an object of size comparable to the Cayley graph) but it does indicate a need for some care.