What is wrong with King David calling the Torah a song (tehillim 119:54, Sotah 35a) when the Torah calls itself such (Devarim 31:19, Nedarim 38a)
Great question! The answer lies in the difference of the words themselves used in the verses (both Hebrew and English provided by mechon-mamre):
1) Tehillim (119:54)- "זְמִרוֹת, הָיוּ-לִי חֻקֶּיךָ--בְּבֵית מְגוּרָי...Thy statutes have been my songs in the house of my pilgrimage."
2) Devarim (31:19) "וְעַתָּה, כִּתְבוּ לָכֶם אֶת-הַשִּׁירָה הַזֹּאת, וְלַמְּדָהּ אֶת-בְּנֵי-יִשְׂרָאֵל, שִׂימָהּ בְּפִיהֶם: לְמַעַן תִּהְיֶה-לִּי הַשִּׁירָה הַזֹּאת, לְעֵד--בִּבְנֵי יִשְׂרָאֵל. "
This difference of terminology is explained beautifully by Rabbi Frand:
The Gaon answers that there exists a tremendous difference between "Zemirah" and "Shirah". Zemirah, like the Zemiros of Shabbos, are finite. They have a beginning and end. [Kah Ribbon (a Sabbath song) starts with a Yud, it ends with a Lamed -- and it's over. All Zemiros are similar.] Shirah represents the infinite. Shirah represents the articulation and expression of feelings, which have no end and no beginning. When a person breaks out in Shirah, it is a manifestation of what his essence is all about. There is no end to that. It is not finite. Torah can be called Shirah, but Torah can not be called Zimra. To refer to Torah as Zimra has the connotation that there can be a beginning to Torah and an end to Torah and then I would be finished with Torah. That is untrue. Torah can't be finished. Torah is Shirah -- the infinite expression of what a Jew is all about, his innermost essence. That was King Dovid's sin.
R. Samson of Sens explains in his commentary to Ahilot (16:4) that in context of this Midrash, "song" refers to a mere metaphor:
ואף על גב דאיענש דוד על שקרא לדברי תורה זמירות ר"ע משל בעלמא
Note that the pashtanim do not interpret the verse in a negative light, (cf. Radak, Alshikh, and Malbim to Psalms 119:54).
Note also that on a peshat level, Deuteronomy (31:19) likely doesn't refer to the entire Torah, (cf. Rashi, Rashbam, and Ramban there).
In summary, there is no contradiction since on peshat level, the Torah as a whole is not referred to as a song, and furthermore, according to peshat, the verse in Psalms indicates no wrongdoing on the part of Moses. Even according to the Midrash in Sotah, David's intent is interpreted as dismissing the Torah's laws as mere parables; something which Deuteronomy (31:19) does not imply.