На таблицу, 25 млн записей, самая нагруженная в проекте чтение, обновление, добавление добавили индекс (не уникальный, не кластеризованный).
Таблица имеет кластеризованный первичный ключ по полю ID (uniqueidentifier). И множество других индексов и внешних ключей.

Почему собственно после добавления еще одного индекса посыпались дедлоки?

Я это вижу так:

Таблица имеет кластеризованный индекс и новый некластеризованный индекс, который включает столбец Column.
Один коннект нашел строку для обновления с помощью кластеризованного индекса и обновил страницу данных. Теперь он хочет обновить индексную страницу с новым значением Column.

Другой коннект нашел ту же строку в некластеризованном индексе и установил блокировку обновления для этой строки в индексе. Блокировка обновления — это блокировка чтения, которая может удерживаться только одним коннектом. Эта блокировка обновления блокирует первый коннект. Второй теперь хочет получить блокировку обновления также на странице данных, но заблокирован первым процессом.

Но как понять, тогда какой индекс вызовет дедлоки, а какой нет?
Честно говоря впервые ловлю дедлок после добавления индекса.