How can I prevent users from creating new categories?

You should to remove a capability named ‘manage_categories’ from user role or roles, for example:

/**
 * Don't let subscribers add/edit/remove categories.
 *
 * You should call the function once when your plugin or theme is activated.
 *
 * @uses WP_Role::remove_cap()
  */
function remove_subscribers_manage_categories() {
    // get_role returns an instance of WP_Role.
    $role = get_role( 'subscriber' );
    $role->remove_cap( 'manage_categories' );
}