As recently reported [Turiv T. et al., Science, 2013, Vol. 342, 1351], fluctuations in the orientation of the liquid crystal (LC) director can transfer momentum from the LC to a colloid, such that the diffusion of the colloid becomes anomalous on a short time scale. Using video microscopy and single particle tracking, we investigate random thermal motion of colloidal particles in a nematic liquid crystal for the time scales shorter than the expected time of director fluctuations. At long times, compared to the characteristic time of the nematic director relaxation we observe typical anisotropic Brownian motion with the mean square displacement (MSD) linear in time $tau$ and inversly proportional to the effective viscosity of the nematic medium. At shorter times, however, the dynamics is markedly nonlinear with MSD growing more slowly (subdiffusion) or faster (superdiffusion) than $tau$. These results are discussed in the context of coupling of colloidal particles dynamics to the director fluctuation dynamics.