After enabling fips sudo stops working

On a rhel6 system I enabled fips using this guide:

https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/Security_Guide/sect-Security_Guide-Federal_Standards_And_Regulations-Federal_Information_Processing_Standard.html

After rebooting the system the sudo entries are not working any more.

Entry in sudoers:

example        ALL=(ALL)       ALL

Example of command run using sudo:

sudo ls -l /root
[sudo] password for example: 
/var/cache/.security.db: unable to flush: Permission denied
sudo: PERM_ROOT: setresuid(0, -1, -1): Operation not permitted
sudo: unable to open /var/db/sudo/example/2: Operation not permitted
sudo: unable to send audit message: Operation not permitted
sudo: unable to set supplementary group IDs: Operation not permitted
sudo: unable to execute /bin/ls: Operation not permitted

Another error when a script is run using sudo, using this entry in sudoers:

example         ALL=/usr/local/bin/example_script.sh

Result:

sudo /usr/local/bin/example_script.sh
[sudo] password for example:
sudo: PERM_ROOT: setresuid(0, -1, -1): Operation not permitted
sudo: unable to open /var/db/sudo/example/1: Operation not permitted
sudo: unable to send audit message: Operation not permitted
sudo: unable to set supplementary group IDs: Operation not permitted
sudo: unable to execute /usr/local/bin/example_script.sh: Operation not 

Possibly relevant log entries:

examplehost sudo: pam_krb5[30799]: authentication succeeds for 'example' (example@exampledomain)
examplehost sudo: example : unable to open /var/db/sudo/example/2 : Permission denied ; TTY=pts/2 ; PWD=/home/example ; USER=root ; COMMAND=/bin/ls -l /root
examplehost example : TTY=pts/2 ; PWD=/home/example ; USER=root ; COMMAND=/bin/ls -l /root
examplehost sudo: pam_keyinit(sudo:session): Unable to change GID to 0 temporarily examplehost su: pam_unix(su-l:session): session closed for user example
examplehost su: pam_unix(su-l:session): session closed for user example

Note, the system is using active directory authentication.

I tried moving /var/db/sudo and /var/cache/.security.db out of the way, with no effect.

Existing entries in sudoers as well as newly created ones are affected. I've looked around but haven't been able to find any solution yet. The system is working fine otherwise, it accepts ssh log in, the webserver is running as well.

Limits appear to be fine:

ulimit -u
31353

cat /etc/security/limits.d/90-nproc.conf

*          soft    nproc     1024
root       soft    nproc     unlimited