Being the curious type, I started to look at whether there was anything consistent with the AVIs that did not play. You can get mplayer to spit out the details with this;
mplayer -endpos 0 -vo null -ao null somevideo.avi
What I discovered is that the ones that would not play all had a commonality to do with the AUDIO codec information. For example if you grep for AUDIO in the output of the mplayer example above, you might get something like;
AUDIO: 48000 Hz, 2 ch, floatle, 128.0 kbit/4.17% (ratio: 16000->384000)
OR
AUDIO: 48000 Hz, 2 ch, floatle, 127.4 kbit/4.15% (ratio: 15927->384000)
All the ones that the Bravia could not play had a sort of exact whole number kbit rate. eg. the AVI with 128.0 kbit in the AUDIO codec info would not play, but the one with 127.4 kbit would play. I found other numbers that seemingly would deter the Bravia from playback; 112.0 kbit and possibly 96.0 kbit.
So then I tried using mencoder in copy mode to see whether that would 'clean up' the AVI files to make them playable and sure enough it actually worked. The Bravia could play them.
mencoder -ovc copy -oac copy -o somevideo-modded.avi somevideo.avi
mencoder in copy mode is incredibly quick. It only takes a few seconds on a 350MB AVI file on a modern machine.
I have actually found a few other AVI's that don't have a magic whole number for the AUDIO codec info and they don't play on the Bravia for some reason .... but running them through mencoder in copy mode does seem to fix them as well.