Travis-CIでapt-get installに失敗する時の対処法

最近はTravisCIでの不可解なエラーのためgem update bundlerを追記する対応が必要になり話題となりましたね。
なんと今度は、今まで動いていたapt-get installが、次のメッセージで失敗するようになりました。

E: Unable to locate package libgeoip-dev

さて、困りました。
早速対処法を探ります。