Пересобирать надо пакеты с libicu56, в том числе и ваши. Займитесь.

Поскольку соседи по /usr/src/debug/
имеют версию в названии:
hunspell-1.3.1
icu
json-glib-1.0.4
keyutils-1.5.9
тут явно какая-то бага в упаковке.

Поскольку, как выяснилось, это зависит от
%setup -n icu
предлагаю заменить на
%setup

чтобы использовалось %name-%version.

Пожалуйста, делайте c icu5.1 что хотите, в новой библиотеке всё останется как есть.

(В ответ на комментарий №4)
> Пожалуйста, делайте c icu5.1 что хотите
Это ситуация будет повторяться с каждой версией.

> в новой библиотеке всё останется как есть.
Аргументы?

Похоже, что это единственный кривой в плане debuginfo пакет.

(В ответ на комментарий №4)
> Пожалуйста, делайте c icu5.1 что хотите,
> в новой библиотеке всё останется как есть.
Почему?

(In reply to comment #3)
> Поскольку, как выяснилось, это зависит от
> %setup -n icu
> предлагаю заменить на
> %setup
> 
> чтобы использовалось %name-%version.

В этом пакете атипичный тарболл (имя каталога просто icu без версии).
В rpmbuild для таких случаев есть документированная магия, можно применить:

%setup -c
%setup -DTn %name-%version/icu

Я понимаю, что никто не использует -debuginfo, но я систему уже месяц не могу обновить.
нельзя ли исправить пакет согласно предложенному плану?

(В ответ на комментарий №8)
> Я понимаю, что никто не использует -debuginfo, но я систему уже месяц не могу
> обновить.
> нельзя ли исправить пакет согласно предложенному плану?
Виталий, вот смотри:
1. Есть таск, решающий эту проблему:
#160166 FAILED #10 sisyphus del=icu5.1 ICAClient-preinstall.git=13.0.0.256735-alt3 del=boost1_53_0
2. Для его успешного выполнения требуется пересборка blender, который у нас не пересобирается в нынешнем виде
3. Глеб сделал нормальную сборку blender, но она требует python3.5, который соберётся неизвестно когда.

Итак, есть следующие варианты:
а) самому поправить icu5.1, если невмоготу ждать;
б) исправить сборку blender в Sisyohus до сборки python3-3.5;
в) сидеть и ждать, пока само рассосётся при сборки нового python3 и blender.

> Виталий, вот смотри:
> 1. Есть таск, решающий эту проблему:
> #160166 FAILED #10 sisyphus del=icu5.1
Ну чего вот придумывать. Есть полиси https://www.altlinux.org/Shared_Libs_Policy, по которому мы определённым образом именуем пакеты библиотек: lib%name%abiversion
И делаем мы это для того, чтобы была возможность размещать новые версии библиотек (несколько версий библиотек), без требования к пересборке всех программ с новой версий (иногда это невозможно).
Так вот давайте этому полиси следовать, а не рассказывать, что что проблему конфликта нескольких версий библиотек легко решить удалением старой библиотеки.

Это не решение проблемы, поскольку суть проблемы в другом.
Это не решение, потому что при следующем обновлении будут те же самые грабли.

icu5.1-1:5.1.1-alt6 -> sisyphus:

* Wed Apr 13 2016 Andrey Cherepanov <cas@altlinux> 1:5.1.1-alt6
- Set different path to sources to fix debuginfo conflicts (ALT #31778)