Create a type for your Enum before the class definition and refer to this type in the map-key.
Code:
<hibernate-mapping package="test.mapwithusertypekey">
<typedef name="map_key_enum_type" class="test.mapwithusertypekey.GenericEnumUserType">
<param name="enumClass">test.mapwithusertypekey.MapKeyEnum</param>
</typedef>
<class name="Parent" table="mwutk_parent">
<map name="valuesMap" table="values_map">
<key column="parent_id"/>
<map-key column="map_key" type="map_key_enum_type"/>
<element column="map_value" type="string"/>
</map>
...
</class>