You need to compile vim with multi-byte support.
The easiest way to do this is to run
./configure --with-features=big
make
This will build vim with the correct support.
You can verify that it was compiled correctly with
:version
in vim or by running
vim --version
and looking for +multi_byte. If it says -multi_byte it will not work.