Sounds like the font files themselves in that folder were system links  so the fonts actually live elsewhere. In general, you do *not* want to change the folder structure outside of your /usr/home/USERNAME folder since the package management & OS rely on it.

I’d start by fining which package installs the font and creates the symlinks and then force install it. For Debian-based distros, I often use the Ubuntu package search to see which package contains the files I’m looking for. In this case, it looks like “font-dejavu-core”: http://packages.ubuntu.com/wily/all/fonts-dejavu-core/filelist

If the font is back, then the issues related to GEM looking in the wrong path could be fixed via IOHannes or some GEM dev updating/making a new font search path to GEM. In the meantime, you can do a quick and dirty fix by making a symlink from the new font dir to the one GEM is looking for:

sudo ln -s  /usr/share/fonts/truetype/dejavu/ /usr/share/fonts/truetype/ttf-dejavu/