I had similar problem (with icaclient 13.0) under Ubuntu 14.04 LTS. Like javy666, regardless what I did with certificates, I was still getting this error. I have installed them correctly into /opt/Citrix/ICAClient/keystore/cacerts, then I did the rehash with "c_rehash /opt/Citrix/ICAClient/keystore/cacerts", I have also updated directories /etc/ssl/certs/ and /usr/share/ca-certificates/mozilla/ and run update-ca-certificates. Google advised a lot of things that did not help, the same error message still persisted. Then I found out that the problem in my case was that my icaclient did not support SHA256 certificates (it did not support any SHA-2 certificates). The message is unfortunately very misleading, it is probably re-used for multiple different situations. I found out that newer version of icaclient (13.3) supports SHA-2 keys, so upgrading of icaclient solved the problem.
It might not solve all the occurrences of this error, but at least some of them.
The reason why this may appear just now more frequently is that SHA-1 are not very secure so logically servers migrate to new SHA-2 certificates, which have poor support in slightly older ICA clients and this produces this misleading error. In my case, our company upgraded intermediate certificates to SHA256, unfortunately at the same time they disabled HTML5 client (probably for compatibility reasons related to SHA256), so Citrix was suddenly completely broken in Linux.