you could use a program such as MediaInfo (link)
to compare the avi files that are working against those that are not, and find out what codec is used for the audio and video streams. might help you identify which codec your TV is having trouble playing. But as you said, UMS should be able to transcode accordingly.
Also, as Seti mentioned, a mini PC might be a better option for your frontend if you can afford it and incorporate it into your setup. You could run a full OS on the box that would be able to handle more media types without needing the transcoding.
If I have some time tonight maybe I'll take a look at UMS again, it's been a while since I've used it. and If you can get the info on the codecs used in your avi files post it so we can see.