I created a custom post type. On the Taxonomies tab of the post type, I selected 4 taxonomies and saved the post type. Nothing happened, the taxonomies didn't get listed under the post type menu.
Then I went to the Post Types tab of one of the taxonomies, and I selected the post type. This worked fine. However, still nothing is selected on the Taxonomies tab of the post type.
So in short: I can only assign taxonomies to post types when I edit the taxonomy, not when I edit the post type.
I have the latest versions of the plugins.