vi visual mode doesn't work

RedHat based systems have a package called vim-minimal installed by default, which has a limited set of features enabled. You want to install the vim-enhanced package.

Debian based systems do something similar, where vim-tiny is the default install and has a minimal feature set. Your Ubuntu system must have one of the other Vim packages installed (likely vim or vim-gtk) which is why it works fine there.

Well it actually seems like you can build vim without support for visual mode. Check the output of :ver and see whether it says +visual or -visual. Bad luck if it's the latter.

I've installed vi as vim-enhanced, but if I run it as vi, :ver shows Tiny version without GUI and lists -visual. When launched as vim, it says Huge version without GUI (and +visual).

Check your .bashrc for alias vi='vim'.