Для тех у кого будет такая же проблема. Я так и не понял почему checkinstall не подтягивает при сборке все зависимости в собираемый .deb пакет, но если возникает ошибка Nginx связанная с библиотекой libbrotlidec.so.1, то ее нужно установить вручную отдельно.
sudo apt install libbrotli1