RNA recognition by proteins is often accompanied by significant changes in RNA dynamics in addition to conformational changes. However, there are very few studies which characterize the changes in molecular motions in RNA on protein binding. We present a quantitative C-13 NMR relaxation study of the changes in RNA dynamics in the pico-nanosecond time scale and micro-millisecond time scale resulting from interaction of the stem-loop SRE-RNA with the VTS1p-SAM domain. C-13 relaxation rates of the protonated carbons of the nucleotide base and anomeric carbons have been analyzed by employing the model-free formalism, for a fully C-13/N-15-labeled sample of the SRE-RNA in the free and protein-bound forms. In the free RNA, the nature of molecular motions are found to be distinctly different in the stem and the loop region. On binding to the protein, the nature of motions becomes more homogeneous throughout the RNA, with many residues showing increased flexibility at the aromatic carbon sites, while the anomeric carbon sites become more rigid. Surprisingly, we also observe indications of a slow collective motion of the RNA in the binding pocket of the protein. The observation of increased motions on binding is interesting in the context of growing evidence that binding does not always lead to motional restrictions and the resulting entropy gain could favor the free energy of association.