Solving complex equations with variable exponents

As stated in the question and also the comment above by Szabolcs, Mathematica does not seem to be able to solve the equation directly. For instance, neither Solve nor Reduce produces the desired result. However, as I suggested in a comment above, the equation can be decomposed into expressions for its amplitude and phase, and each solved to obtain the answer. Begin with the amplitude.

Abs[(1 + I)]^n == Abs[(1 + Sqrt[3] I)]^m
(* 2^(n/2) == 2^m *)

Thus, n is twice m. Insert this into the expression for the phases, modulo 2 π.

Solve[(Mod[Arg[(1 + I)] n, 2 π] == 
    Mod[Arg[(1 + Sqrt[3] I)] m, 2 π]) /. n -> 2 m, m, Integers]
(* {{m -> ConditionalExpression[12 C[1], C[1] ∈ Integers]}} *)

This, m is any integer, positive or negative, multiplied by 12, and n is 2 m.

One can get a truly ridiculous solution by ComplexExpand[]ing the real and imaginary parts:

Reduce[ComplexExpand[{Re /@ #, Im /@ #}] &[
    (1 + I)^n == (1 + Sqrt[3] I)^m], 
  {m, n}, Integers]
(*  ... an astonishing mess involving 14 integer parameters ... *)

However, pulling out the magnitude and argument is much nicer.

Reduce[ComplexExpand[{Abs /@ #, Arg /@ #}] &[
    (1 + I)^n == (1 + Sqrt[3] I)^m], 
  {m, n}, Integers]
(* C[1] ∈ Integers && m == 12 C[1] && n == 24 C[1] *)

(This essentially automates @bbgodfrey's answer.)

Last@Reap@Do[
  If[
   ReIm[(1 + I)^n] == ReIm[(1 + Sqrt[3] I)^m]
   , Sow[{n, m}]
   ]
  , {n, 100}
  , {m, 100}
  ]

{{{24, 12}, {48, 24}, {72, 36}, {96, 48}}}