never really had the PS3 struggle with WMVs(surprisingly enough), you just need to do the liscensing thing in the settings in order for it to work. AVIs on the other hand, the PS3 is very finiky of their encoding. An AVI is basically a folder holding a music format type and a video format type and going at a relative speed of some sort. If they aren't to PS3 standards it will not play. I too have had to re-encode a few videos, or even just turn to simple MP4 in order for it to play.
Another note: If you have IPOD encoded MP4s, they will not work on PSP or PS3(to my knowledge) but there is a program specifically made for PSP that will format it to the right type. Any Video that will Play on PSP will play on PS3.
Greatness Awaits
PSN:Forevercloud (looking for Soul Sacrifice Partners!!!)