Solution for MySQL ERROR 1396 (HY000): Operation CREATE USER failed for

This indicates that the user already exists, or did exist but that all of the data for that user has not been deleted.

As the mysql root user:

REVOKE ALL PRIVILEGES, GRANT OPTION FROM 'user'@'hostname';
DROP USER 'user'@'hostname'

Then re-try creating the user.