I'm trying to create category values using RQM REST and the JAXB classes generated from the QM schemas.  From examining the XML content of the  /category and /categoryType feeds:

1.  What the qm UI calls a category is  CategoryType (JAXB class)
2.  What the qm UI calls a category value is a Category (JAXB class)
3.  A Category is associated with a CategoryType.

I'm able to create categories by POSTing CategoryType objects:
CategoryType catType = new CategoryType();
catType.setTitle("Country");
catType.setProjectArea(projectArea);
catType.setScope("TestPlan");
catType.setRequired(false);
catType.setMultiSelectable(false);

I'm dead in the water trying to create and associate values, i.e., create and associate a Category with a CategoryType. 

As far as I can tell, you make the association by invoking setCategoryType() on the Category.  The challenge is that the argument to setCategoryType()  needs to be a Category.CategoryType -- not the CategoryType used to create the CategoryType.