What's wrong with the Foreign Key Constraint in this table?

Your column id is int unsigned; your column parent_id is int. Those don't match. The solution is to change parent_id to be int unsigned as well.

If you run the SHOW ENGINE InnoDB STATUS I put in a comment, you see this:

11005 17:18:38 Error in foreign key constraint of table test/genre:

    FOREIGN KEY (`parent_id` )
    REFERENCES `genre` (`id` )
    ON DELETE SET NULL
    ON UPDATE CASCADE)
ENGINE = InnoDB:
Cannot find an index in the referenced table where the
referenced columns appear as the first columns, or column types
in the table and the referenced table do not match for constraint.
Note that the internal storage type of ENUM and SET changed in
tables created with >= InnoDB-4.1.12, and such columns in old tables
cannot be referenced by such columns in new tables.
See http://dev.mysql.com/doc/refman/5.1/en/innodb-foreign-key-constraints.html
for correct foreign key definition.

Note the "column types in the table and the referenced table do not match" part.

The two fields are not the same type.

CREATE  TABLE IF NOT EXISTS `genre` (
  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,  <<-- unsigned int
  ..
  ..
  `parent_id` INT NULL DEFAULT NULL ,        <<-- signed int
  PRIMARY KEY (`id`) ,                   ***** not the same!!!!
  ....

id is UNSIGNED but parent_id is not unsigned.