Are you sure this is an overall Leopard problem and not just your specific setup? It's not the same printer, but I have an IP4300 on an AEBS, and it prints fine from two different machines on Leopard.
I did, however, have to re-set it up after the upgrade (though in my case it wasn't printing at all). If you haven't already tried this, you might see what happens if you remove the printer from the AEBS and your Mac(s), reinstall the driver for the heck of it, re-attach it, and re-add it to the list of printers.