Nanostructured rare-earth-ion doped materials are increasingly being investigated for on-chip implementations of quantum information processing protocols as well as commercial applications such as fluorescent lighting. However, achieving high-quality and optimized materials at the nanoscale is still challenging. Here we present a detailed study of the restriction of phonon processes in the transition from bulk crystals to small ($le$ 40 nm) nanocrystals by observing the relaxation dynamics between crystal-field levels of Tb$^{3+}$:Y$_3$Al$_5$O$_{12}$. We find that population relaxation dynamics are modified as the particle size is reduced, consistent with our simulations of inhibited relaxation through a modified vibrational density of states and hence modified phonon emission. However, our experiments also indicate that non-radiative processes not driven by phonons are also present in the smaller particles, causing transitions and rapid thermalization between the levels on a timescale of $<$100 ns.