Примерно такая же проблема.
Есть беспроводной роутер D-Link 824VUP+ к которому подсоединен принтер.
На офф. сайте Д-линка написано: тип очереди UNIX (LPD), сервер ххх.ххх.ххх.ххх (IP-адрес роутера), очередь LP.
Запустил Nmap - выдает: 515/tcp open printer
В каких комбинациях не пробовал это прописать - не получается. А сейчас вообще не могу создать новый принтер в "Настройка принтера".
Upd: Проблема решиалсь. Оказалось достоточно написать в форум и... перезагрузиться. И все заработало.

Работающая настройка: URI устройства lpd://xxx.xxx.xxx.xxx/lp (x-адрес роутера). И все. Даже на маке у меня эта настройка больше времени заняла в свое время..
PS. Никак не могу найте в Ubuntu что-то, что плохо работает. Поставил попробовать пару дней назад и до сих пор нахожусь в состоянии легкого шока. Когда при загрузке с live_CD он подцепил WiFi-карту, вышел в сеть и я мог спокойно устанавливать ось (напр. менять разделы на жестком диске), одновременно читая в сети о том, как это правильно сделать. Драйвер для видеокарты - пожалуйста. Кодека нет нужного - сам скачать предлагает. Не, я правда в шоке. Еще очень поразило, когда во время каких-то настоек в терминале, он мне вдруг заявил по-русски (!), что, мол приложение xxx не установлено, чтобы его установить, наберите... До сих пор отойти не могу