Sorry to butt in, but I had this before and it had me confused too! You need to set permissions for your category before it will be recognised (and displayed in the "parent" dropdown menu)
Hope this helps!
Edit: didn't read the permissions part in the above poster's post. My bad. You can delete this