This FAQ diagnosed the problem - I had to re-mux the AVI. Unfortunately it only had instructions for Windows.
To fix this in Ubuntu Linux I ran the following two commands:
sudo aptitude install mencoder
mencoder -ovc copy -oac copy -of avi -o "remuxed.avi" "original.avi"
The file processed for a few minutes and then it ran smoothly on XBMC.