The substitution of aluminum oxide into rutile (TiO2) has major effects on crystal growth, cation diffusivity, and conductivity and, critical for its widespread application as a white pigment, inhibits photocatalytic activity. High-field, high-resolution Al-27 NMR provides unique constraints on the type and concentrations of several Al sites in rutile. For samples ranging from about 0.2 to 1 wt % Al2O3, annealed at 1000-1500 degrees C, Al in ordered, isolated octahedra (Ti sites) can be quantified. At the higher concentrations, Al in other disordered octahedral sites becomes predominant and may be due to both Ti sites with Al neighbors and to interstitials. The NMR line shape of this disordered component resembles that of Al2TiO5, for which new data are also presented. In all rutile samples, significant concentrations of Al in four-coordinated sites (and possibly in five-coordinated sites) are detected. In samples doped with equimolar Nb2O5, Al in isolated Ti sites is predominant at all concentrations. Temperature has only minor effects on relative concentrations of Al species, but strongly affects total solubility. In samples with excess or exsolved alpha-Al2O3 (corundum), solubility at 1200 degrees C is 0.56 +/- 0.04 wt % and at 1000 degrees C is 0.23 +/- 0.02 wt %.