We investigate long-time translational and rotational self-diffusion of fluorocarbon tracer spheres (100 nm radius) in aqueous dispersions of silica host spheres (10 nm radius). Diffusion is measured as a function of ionic strength (0-10 mM NaCl) and for host-sphere volume fractions up to 37% using depolarized dynamic light scattering. Both translational and rotational self-diffusion are strongly hindered and have a similar concentration dependence as the low-shear viscosity, except at the lowest ionic strength. Our results show that the Stokes-Einstein (SE) relations, linking viscosity and diffusion at infinite dilution, can be extended to dense colloidal systems whenever the dynamics of the host spheres is fast compared to the experimental time scale. However, when the host-sphere dynamics is relatively slow, such as in the case of very large host particles or charged particles at low ionic strength, tracer-sphere diffusion (in particular rotation) generally is faster than the SE relations.