The title is the message i get for any video i have tried to play on the web or any song i downloaded and try to play. I just got this phone today too and videos and songs were working earlier in the day, and don't know what changed.
See if the new 2.3.34 Verizon update is available.
Control Button->Settings->About Phone->System Updates
See if under System version what number is there. If its not Version.2.3.340.MB810.Verizon.en.US then click on System Updates on the top and update it. If it says you are up-to-date then you have to wait until Verizon rolls the update out to your phone.
There is a problem with the MP3 and DivX codecs on the stock version. If it is up-to-date then pull the battery, and restart to see if that fixes the problem.