Printing to Lexmark 5400 via D-Link DIR20 router

Anyone had problems trying to print to a (vista compliant) Lexmark on a
network?

After all the problems we had caused by Vista's pathetic networking
capabilities we finally thought replacing the hub we were using with a
router had fixed it by giving Vista something easier to play with, when all
computers were suddenly working properly and seeing one another. But no.
Vista cannot print successfully to the printer (from any machine) when it is
connected to the USB port on the router. All computers (2xVista, 1xXP) are
connected correctly, all can access the internet and each other, but we
can't add the printer successfully to the network. When you print a test
page it says "printing started" and "printing complete" without doing
anything. It briefly shows the Lexmark box that tells you the ink cartridges
are out of ink when they are not, and the print job is listed as "sent to
printer" but remains in the queue.