Have you really deleted the user of just deactivated it?
Deleting the user should cause JIRA to remove all entries from the user, so this message being displayed is somewhat a bug, but if you disabled the user, then you can re-enable it by selecting your User Management to display Inactive Users and activate the user again.
If this does not apply to you, you can let me know your instance URL and the username so I can verify this behaviour for you.
Also, please feel free to raise a Support Ticket at Atlassian Support:
Connect with like-minded Atlassian users at free events near you!Find a group
Connect with like-minded Atlassian users at free events near you!
Unfortunately there are no AUG chapters near you at the moment.Start an AUG