Well, I managed to keep all the other applications by just ignoring the error. Done like the this:

# apt-get remove vcmi-bin vcmi-data vcmi
# apt-get update
# apt-get install vcmi

That way it's installed with some warning regarding the libsdl-ttf2.0 thing, but it's installed and works fine... Tried that?