Do you have the latest version of VLC? They released a patched version 0.8.6a to fix all the problems people had with 0.8.6.
MPlayer OS X could also be worth a look although personally I prefer VLC.
You could also install Perian which is an all in 1 codec pack for Quicktime. I have Perian, AC3, and Flip4Mac installed here for QT and that seems to handle nearly everything VLC can.