I am facing the same problem, but with a more simple setup:
– No custom post type set, just a normal post
– Any category / subcategory seems to act this way
When creating a new post the categories are listed are they are supposed to: subcategories are nested below their parents. Selecting either the parent or the subcategory alone and publishing or saving a draft of the post like that causes the categories to be listed at the bottom of the category list without being nested like they are supposed to. It gets fixed when either the parent category or the subcategory is added and the post updated.
Using WordPress 3.3.1 (in Finnish).