Order entries by category field
Here's a solution using the group filter.

{% set entriesGrouped = craft.entries.relatedTo(category).order('title')|group('myNewCategoriesField.first().title') %}

{% for group in entriesGrouped %}
    {% for entry in group %}

        {# ... #}

    {% endfor %}
{% endfor %}