Where is the code that catches an processes the $_POST data? Is it in a template file? Or is it in a function that is run on a hook? If it’s the latter, and if taxonomy_exists() is returning false as you suggest here (http://wordpress.stackexchange.com/questions/45798/wp-insert-post-and-custom-taxonomy#comment58402_45810), it’s possible that you’re checking before register_taxonomy has had a chance to run. Make sure that your form-processing function is hooked to something later than init:10.
