It is known that the following three computational problems for subgroups $G$ of $S_n$ are polynomially equivalent:

 1.  Computing (generators of) the centralizer $C_G(g)$ of an element $g \in S_n$ (and also testing $g,h \in S_n$ for conjugacy in $G$).

 2. Computing (generators of) the setwise stabilizer of a subset of the set of size $n$ on which $S_n$ acts (and also testing two such subsets for being in the same orbit under $S_n$).

 3. Computing (generators of) the intersection of $G$ with another subgroup $H \le S_n$.

As Mark says, these are all at least as difficult as graph isomorphism.

The proofs are clever but basically elementary and interesting, so I recommend them! One reference is: 

E.M. Luks, ``Permutation groups and polynomial-time computation'',
in L. Finkelstein and W.M. Kantor (eds.), Groups and Computation,
Dimacs Series in Discrete Mathematics and Theoretical Computer Science
vol. 11, American Math. Soc., 139-176, 1993.

I have just noticed that Luks has a recently published book with the same title, which I have not seen yet.