We study the microscopic viscoelastic properties and relaxation dynamics of solutions of a side-chain associative polymer, hydrophobically modified hydroxyethyl cellulose (hmHEC). Dynamic light scattering from small tracer particles suspended in the polymer solutions is used to determine their viscous and elastic moduli on the scale of the particles. Bulk-scale viscoelastic properties are measured by shear rheometry. The motion of the tracer particles in hmHEC is diffusive at short times and subdiffusive at intermediate and long times. The long-time subdiffusive motion was not observed in parallel experiments on unmodified HEC solutions, and is explained in terms of hindered reptation of the hydrophobically modified polymer chains in the associative network. Dynamic light scattering from the polymer molecules themselves shows that chain relaxation in hmHEC is dominated by slow concentration-dependent processes due to the large-scale associative network structure, while that in HEC is dominated by fast concentration independent Rouse-like dynamics.