How to fix Video tearing with KDE and ati drivers?
The AMD Catalyst software has an option to reduce tearing.
Open a terminal and type kdesudo amdcccle, then find the section for reducing tearing and check the option.
Additionally, I should mention that I had some tearing issues with VLC and Totem a while ago (before the 13.1 driver was released), but using smplayer instead of VLC dramatically improved my video playback. If the Catalyst option doesn't work for you, give smplayer a try and see if that helps.