Hi,
 Could you attach the output of:
$ gnutls-cli www.google.com --priority @SYSTEM

Created attachment 1080870 [details]
rhbz-1269453-gnutlscli-dump.txt

Requested gnutls-cli output

Created attachment 1080871 [details]
rhbz-1269453-gnutlscli-tic.sixxs.net.txt

gnutls-cli mimicking AICCU session establishment.

That's a bit strange since gnutls-cli seems to work. Can you do:
$ export GNUTLS_DEBUG_LEVEL=99
$ _run aiccu_

Trying to build aiccu from the fedora rep brings up:
> error: Bad source: /home/nmavrogi/fedora/aiccu/aiccu-gnutls34.patch: No such file or directory

So, that looks like an issue with the aiccu fedora package. Feel free to reassign back if that's not the case.

# aiccu start
gnutls[2]: Enabled GnuTLS logging...
[GNUTLS] REC[0xae7ec0]: Allocating epoch #0

[GNUTLS] selected priority string: NONE:+VERS-TLS-ALL:-VERS-SSL3.0:+AEAD:+SHA1:+SHA256:+SHA384:+ECDHE-RSA:+ECDHE-ECDSA:+RSA:+DHE-RSA:+DHE-DSS:+AES-256-GCM:+AES-256-CCM:+AES-256-CBC:+CAMELLIA-256-GCM:+CAMELLIA-256-CBC:+AES-128-GCM:+AES-128-CCM:+AES-128-CBC:+CAMELLIA-128-GCM:+CAMELLIA-128-CBC:+3DES-CBC:+SIGN-ALL:-SIGN-RSA-MD5:+CURVE-ALL:+COMP-NULL:%PROFILE_LOW

[GNUTLS] ASSERT: gnutls_priority.c:1391

[GNUTLS] ASSERT: gnutls_handshake.c:2527

TLS Handshake failed: No or insufficient priorities were set. (-326)
Couldn't retrieve first tunnel for the above reason, aborting

That's certainly a strange error if this is the only text printed out. 

However, looking at your report, it is a bit confusing which distro are you using. Is that f24 or f22? F22 with some f24 packages wouldn't work.

crypto-policies-20151005-1.gitc8452f8.fc24.noarch
gnutls-3.4.5-1.fc24.x86_64
aiccu-2007.01.15-22.fc22.x86_64

(In reply to Nikos Mavrogiannopoulos from comment #7)
> That's certainly a strange error if this is the only text printed out. 
> 
> However, looking at your report, it is a bit confusing which distro are you
> using. Is that f24 or f22? F22 with some f24 packages wouldn't work.
> 
> crypto-policies-20151005-1.gitc8452f8.fc24.noarch
> gnutls-3.4.5-1.fc24.x86_64
> aiccu-2007.01.15-22.fc22.x86_64

It looks like the last aiccu build is fc22.

Ok, then it seems it is depending on the compat-gnutls28 package which cannot parse the default priorities set in rawhide. You'll need a new build for aiccu in f23 and f24 to link with the latest gnutls version shipped.

compat-gnutls28-3.3.18-1.fc23 has been submitted as an update to Fedora 23. https://bodhi.fedoraproject.org/updates/FEDORA-2015-88bb879cab

compat-gnutls28-3.3.18-1.fc23 has been pushed to the Fedora 23 testing repository. If problems still persist, please make note of it in this bug report.
If you want to test the update, you can install it with
$ su -c 'dnf --enablerepo=updates-testing update compat-gnutls28'
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2015-88bb879cab

compat-gnutls28-3.3.18-1.fc23 has been pushed to the Fedora 23 stable repository. If problems still persist, please make note of it in this bug report.

Just for the records...for those which have same issues e.g. on EL7 (aiccu is neither in RHEL repo nor in EPEL) by using a rebuilded SRPMS from F25 (e.g. aiccu-2007.01.15-26.fc25.src.rpm), here is a fix which solves the problem:

--- aiccu/common/common.c	2017-01-27 20:49:53.638592763 +0000
+++ aiccu.patched/common/common.c	2017-01-27 21:15:27.767674752 +0000
@@ -295,8 +295,7 @@
 	}
 
 	/* Use default priorities */
-	/* Allow connections to servers that have OpenPGP keys as well */
-	gnutls_priority_set_direct(sock->session, "@SYSTEM", NULL);
+	gnutls_set_default_priority(sock->session);
 
 	/* Configure the x509 credentials for the current session */
 	gnutls_credentials_set(sock->session, GNUTLS_CRD_CERTIFICATE, g_aiccu->tls_cred);