Why does rpc.svcgssd fails when setting up Kerberized NFSv4 ?

Issue

Setting up Kerberized NFS on a server. Adding principles and their entries in krb5.keytab is successful. The next step is to restart nfs service for the changes to take effect:

# service nfs restart
Shutting down NFS mountd:                                  [  OK  ]
Shutting down NFS daemon:                                  [  OK  ]
Shutting down NFS quotas:                                  [  OK  ]
Shutting down NFS services:                                [  OK  ]
Shutting down RPC svcgssd:                                 [FAILED]
Starting RPC svcgssd:                                      [FAILED]
Starting NFS services:                                     [  OK  ]
Starting NFS quotas:                                       [  OK  ]
Starting NFS daemon:                                       [  OK  ]
Starting NFS mountd:                                       [  OK  ]

If we have a look in the /var/log/messages we find the following errors:

May 20 08:25:34 server rpc.svcgssd[20502]: ERROR: GSS-API: error in gss_acquire_cred(): Unspecified GSS failure.  Minor code may provide more information - No principal in keytab matches desired name 
May 20 08:25:34 server rpc.svcgssd[20502]: unable to obtain root (machine) credentials 
May 20 08:25:34 server rpc.svcgssd[20502]: do you have a keytab entry for nfs/<your.host>@<YOUR.REALM> in /etc/krb5.keytab? 

The error above logically means to check if we have the entry for the nfs service in our keytab. However, when checked, the entry is indeed in the keytab:

# ktutil 
ktutil:  rkt /etc/krb5.keytab
ktutil:  list
slot KVNO Principal
---- ---- ---------------------------------------------------------------------
   1    3            host/server.example.com@EXAMPLE.COM
   2    3            host/server.example.com@EXAMPLE.COM
   3    3            host/server.example.com@EXAMPLE.COM
   4    3            host/server.example.com@EXAMPLE.COM
   5    3            host/server.example.com@EXAMPLE.COM
   6    3            host/server.example.com@EXAMPLE.COM
   7    3             nfs/server.example.com@EXAMPLE.COM
   8    3             nfs/server.example.com@EXAMPLE.COM
   9    3             nfs/server.example.com@EXAMPLE.COM
  10    3             nfs/server.example.com@EXAMPLE.COM
  11    3             nfs/server.example.com@EXAMPLE.COM
  12    3             nfs/server.example.com@EXAMPLE.COM
ktutil:  q