Canon IR Advanced C2020 Won’t Print From a Mac

I’m having an issue with a Canon IR Advanced C2020 on the Mac side. We have the printer connected to the network and printing from Windows machines using the UFRII driver but I can’t seem to get any Macs printing to it. A quick rundown of relevant info:

• It’s assigned a static IP which is pointed to by a hostname.
• It only has UFRII installed, no other printing protocols.
• We haven’t locked any ports on the machine down yet (including LPD/LPR)
• Job accounting is turned on.
• The Mac's are all running 10.6.x with the test machines I've been running at 10.6.6.

Troubleshooting steps taken thus far and their results:

• I was getting an error that stated “Incorrect ID or Password; Specify the correct ID and Password.: 15513” however a Google search around this error wasn’t very helpful. I should also note that no Dept. ID prompt appeared before this error.
• I changed the hostname to an IP address and the error above went away and it started prompting for a Dept. ID again. However when I would print something I would get the following error: “Printer in use. Waiting for the print job to finish” which appeared despite no print jobs running on the printer.
• I’ve tried various different queue names from LP to LP1 to LPD to print and none of them changed the above behavior.
• Disabling the firewall seemed to change the behavior from the 15513 error when a hostname is entered to the print queue error however when I tried that again this morning there was no change so that may have been an unrelated thing.
• I’ve tried the PPD drivers which were useless.
• When I disabled job accounting on the printer and tried to print after re-adding the printer sans job accounting I received the same error that the printer was in use.

I’m really hitting an idea wall and I was hoping someone out there might have an idea as to why this is happening and what I could do to fix it.