Water exchange at Al (III)
I actually tend to agree with the answer from @JanJensen based on electrostatic effects, rather than with the "covalency" argument. 

In particular, it has been mentioned in the comments that the $\ce{Al^{III}-OH2}$ is a "far more covalent" bond than one $\ce{Mg^{II}-OH2}$ one. This remark, however, does not actually explain anything, but rather it shifts the question to a new one, i.e. why is it, then, that the $\ce{Al-O}$ bond is more covalent?

Water exchange reactions at the Mg and Al centers have actually been studied extensively, but unfortunately not to the same extent as those for transition metal ions, or for selected lanthanides. The latter in particular are a subject of continuous and very intense interest, because water exchange at e.g. $\ce{Gd^{III}}$ or $\ce{Eu^{II}}$ ions play a pivotal role in the effectiveness of complexes of these ions as MRI contrast agents. 

Nonetheless, here are a few very relevant references that will certainly offer some more insight, but probably not the final answer that you are looking for. 


An $\ce{^{17}O}$-NMR Study of the Exchange of Water on $\ce{AlOH(H2O)5^{2+}(aq)}$, Inorganic Chemistry, 1998, 37 (19), 4760–4763;
Water exchange on metal ions: experiments and simulations, Coordination Chemistry Reviews, 1999, 187 (1), 151–181.


In fact, when studying exchange reactions at metal ions, the authors of these and other studies tend to consider ions with equal charge as homogeneous series, because the effect of the charge will swamp out any other effect, some times even the relatively large effects of electronic configuration in d-transition metals!

That notwithstanding, the papers above agree that the mechanism for the water exchange reactions for both Al and Mg metal complexes is dissociative in nature, which means that the rate determining step involves the loss of a $\ce{H2O}$ ligand from the inner sphere of the complex. 

We can combine this piece of information with the fact that, as mentioned in the second paper above, there is a significant increase in charge density when going from $\ce{Mg^2+}$ to $\ce{Al^3+}$. First, the aluminum cation is smaller (reported values from that reference are: 72 pm for $\ce{Mg^2+}$ and 53 pm for $\ce{Al^3+}$); secondly, it has higher charge. This rather staggering difference can again be explained using the usual electrostatic arguments (i.e. the two ions are isoelectronic, but the Al nucleus contains more protons, so electrons in the latter are held more closely, leading to smaller cations).

Trying to put this all together: 


removing a water molecule determines the rate of the overall exchange process according to the experimentally determined dissociative mechanism;
the smaller, more highly charged $\ce{Al^3+}$ exerts a much stronger attraction on each of its bound $\ce{H2O}$ ligands, making said removal much more costly; 
in macroscopic terms, the $\ce{Al^3+}$ has a much higher activation energy, which ultimately manifests itself in the much lower rates of exchange that the OP referred to.