Note: This post is 6 years old. Some information may no longer be correct or even relevant. Please, keep this in mind while reading.
This happened to me when embedding an EPS file into a xelatex document. The fix for me was to add the binaries directory /usr/local/texlive/2016/bin/x86_64-linux to the PATH environment variable.