問題が起きた条件としては、Railsのプロジェクトでテストにはpoltergeistを使い、CI上はXvfb, phantomjsを設定していた

解決方法

日本語フォントのインストール
使ったpackageは fonts-ipafont

.travis.yml

sudo: false
addons:
  apt:
    packages:
    - fonts-ipafont

参考

addons apt + sudoなどに関する内容
Installing Packages on Container Based Infrastructure
Travis CI + sudo

他にもfonts-ipafont-gothic, fonts-ipafont-minchoなのどフォントがある docker + capybara-webkit

他の設定

Xvfb

Using xvfb to Run Tests That Require a GUI

phantomjs

Add support for PhantomJS 2
phantomjs --version は上手く動いたなら削除可能と思う（cacheとの兼ね合いか動作が変だったことがある）

全体の設定

動作した設定ファイルからpostgresなどのプロジェクトごとの部分を省略したもの

.travis.yml

language: ruby
cache:
  bundler: true
  directories:
    - "travis_phantomjs"
sudo: false
addons:
  apt:
    packages:
    - fonts-ipafont
before_install:
  - "phantomjs --version"
  - "export PATH=$PWD/travis_phantomjs/phantomjs-2.1.1-linux-x86_64/bin:$PATH"
  - "phantomjs --version"
  - "if [ $(phantomjs --version) != '2.1.1' ]; then rm -rf $PWD/travis_phantomjs; mkdir -p $PWD/travis_phantomjs; fi"
  - "if [ $(phantomjs --version) != '2.1.1' ]; then wget https://assets.membergetmember.co/software/phantomjs-2.1.1-linux-x86_64.tar.bz2 -O $PWD/travis_phantomjs/phantomjs-2.1.1-linux-x86_64.tar.bz2; fi"
  - "if [ $(phantomjs --version) != '2.1.1' ]; then tar -xvf $PWD/travis_phantomjs/phantomjs-2.1.1-linux-x86_64.tar.bz2 -C $PWD/travis_phantomjs; fi"
before_script:
  - phantomjs --version
  - "/sbin/start-stop-daemon --start --quiet --pidfile /tmp/custom_xvfb_99.pid --make-pidfile --background --exec /usr/bin/Xvfb -- :99 -ac -screen 0 1280x1024x16"
  - bundle exec rake db:migrate
script:
  - bundle exec rspec spec