I'd almost forgotten about this, but when I first got a DVD player that would handle DIVX avi's I the same choppy video problem that I sometimes have on my Bold. Some videos play perfectly, while others are so choppy that they're unwatchable.
The fix for the DVD player was to remove get rid of the packed bitstream option used to encode the original video. When I checked, all the videos that were choppy on my Bold had the packed bitstream option.
To get rid of this PITA, all you need to do is run MPEG4 Modifier, and select the unpack option. This takes only seconds, and does not appreciably change the size of the file (usually only a few Kb). Load the unpacked version up on the Bold, and it's nice and smooth!
You can find MPEG4 Modifier here:
MPEG4 Modifier