山本宗宏です。
Ubuntu 16.04 LTS (Xenial Xerus) の distroビルドTeX Live環境において、
xcolor.styがtexlive-latex-recommendedに含まれていました。
https://packages.ubuntu.com/xenial/any/texlive-latex-recommended
texlive-latex-recommended (2015.20160320-1) のdebパッケージを調べてみたところ、
xcolor.sty 2007/01/21 v2.11 LaTeX color extensions (UK)
でしたから、やはりお手元のUbuntu Linux distroビルドのTeX Live環境を再構築なさったほうがよいと存じます。