Ну во-первых, вместо fakeroot debian/rules binary
рекомендую использовать debuild. Он заодно и chmod +x debian/rules сам
сделает (пакет devscripts).
Во-вторых, не рассмотрена проблема версионированных зависимостей в
Build-Depends. Рассмотреть её следует следующим способом
Если при сборке вылетает "хочу версию пакета xxx y.yy, а установлена
только z.zz", то сначала следует попробовать занизить версию в
Build-Depends до доступной, и только если при этом пакет откажется
собираться или работать, бэкпортить соответствующую версию.
Спасибо!
Пополнил.