I think I have the same problem. 
I am using Hardy Alpha 4 (Linux 2.6.24-8-generic #1 SMP Thu Feb 14 20:40:45 UTC 2008 GNU/Linux)
I have been trying to print to a HP LaserJet 1018 which is shared on a windows XP machine via Samba. 
This did not work, so I plugged it directly into my laptop (kubuntu hardy Alpha 4). 
It was detected, and little printer appeared in the tray which said that the printer was installed and ready to use. Ha, it did NOT work! 
After some googling, I found this post on the kubuntu forum (http://kubuntuforums.net/forums/index.php?topic=10654.0;topicseen) 
I followed the instructions to the letter and the printer reset itself when I entered the command to update the firmware. 
I then added the printer using KMenu -> System -> Printing. I was able to print from open office.
I then moved the printer back to the windoze PC and tried to setup the printer again via the add printer wizard through samba.
When I click on the printer test button I get this in the kernel.log file, which seems the same as reported earlier in this post:

==> /var/log/kern.log <==
Feb 18 23:46:10 buks kernel: [38441.820449] audit(1203371170.946:141): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:10 buks kernel: [38441.830251] audit(1203371170.958:142): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:10 buks kernel: [38441.832097] audit(1203371170.958:143): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.886584] audit(1203371171.014:144): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.887012] audit(1203371171.014:145): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.887907] audit(1203371171.014:146): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.891499] audit(1203371171.018:147): operation="inode_permission" request_mask="::rw" denied_mask="::rw" name="/dev/tty" pid=18284 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.901246] audit(1203371171.030:148): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.901994] audit(1203371171.030:149): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.904585] audit(1203371171.034:150): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.918101] audit(1203371171.046:151): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.918137] audit(1203371171.046:152): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.918678] audit(1203371171.046:153): operation="inode_permission" request_mask="::r" denied_mask="::r" name="/var/run/samba/gencache.tdb" pid=18277 profile="/usr/sbin/cupsd" namespace="default"
Feb 18 23:46:11 buks kernel: [38441.924317] audit(1203371171.050:154): operation="inode_permission" request_mask="::rw" denied_mask="::rw" name="/dev/tty" pid=18287 profile="/usr/sbin/cupsd" namespace="default"

==> /var/log/lpr.log <==
Feb 18 23:46:11 buks foo2zjs-wrapper: foo2zjs-wrapper -P -z1 -L0 -r1200x600 -p1 -s7 -m1 -n1
Feb 18 23:46:12 buks foo2zjs-wrapper: gs -sPAPERSIZE=letter -g10200x6600 -r1200x600 -sDEVICE=pbmraw -dCOLORSCREEN -dMaxBitmap=500000000
Feb 18 23:46:12 buks foo2zjs-wrapper: foo2zjs -r1200x600 -g10200x6600 -p1 -m1 -n1 -d1 -s7 -z1  -u 192x96 -l 192x96 -L 0     -P

What now?