Решил проблему так:
Принтер, подключенный к WinXP SP3, использовал в настройках "Прямой вывод на печать" вместо "Печатать в очередь". Прямой вывод на печать исправлял баг, когда все листы документа печатались на 1 странице.
Создал еще одну очередь, связанную с данным принтером, но с настройкой "Помещать документ в очередь полностью и потом печатать".
Проблема печати из Ubuntu 10.10 исчезла ...