Taxonomy, or 'Categories' in 5.x and on, requires a vocabulary to the content type.

Just create a taxonomy (category) and fill it with a perfect array of terms and make sure your content type is assigned the new taxonomy (category) type.

Go to (administer > categories > edit vocabulary) and look under the "Types" heading. There you can assign your taxonomy to any content types you want. Save your configuration here, and try to submit a post. Your taxonomy should now be available in the submission post.