The issue is due to the AppArmor profile of Evince, which restricts the file resources available to Evince.
Because TexLive fonts are made available to the system, they might get picked up by Evince under certain circumstances (on my system, there is a rule defined in /etc/fonts/conf.avail/30-metric-aliases.conf which binds "Tex Gyre Heros" and "Helvetica". Because I don't have the Helvetica font installed, Tex Gyre Heros gets picked up by fontconfig instead).
The error message is somewhat misleading, but if you looked at the kernel logs (type
dmesg in the console, or
tail -f /var/log/syslog), you would see error messages such as:
[345695.334701] type=1400 audit(1462672575.673:72990): apparmor="DENIED" operation="open" profile="/usr/bin/evince" name="/usr/local/texlive/2015/texmf-dist/fonts/opentype/public/tex-gyre/texgyreheros-regular.otf" pid=31050 comm="EvJobScheduler" requested_mask="r" denied_mask="r" fsuid=1000 ouid=0
To give Evince read access permissions to your TexLive fonts, you can add the following rule in the file
Save the file and reload the rule by issuing (in a terminal):
sudo service apparmor reload
and quit any open instance of Evince. The next time you open your PDF file in Evince, it should display your PDF correctly, having access to the needed fonts.