Nickname already exists on the post office?

GW2014, not R2, I changed the surname of one of our users, then changed the
user ID (rename), and wanted to go an setup a nickname for the old user
object to cover the name change.
I go in to the account to create a nickname and get "Nickname xxx already
exists on the post office."

I cannot find this nickname anywhere though. It doesn't show on the user
object that I'm trying to create it on, or in the post office?

The nickname appears to be there working though, the old email address
(firstname.surname) and the new one works, and mail is delivered to the
users mailbox.

Can anyone shed any light on this please?

Thanks, Alan