Printer

I wasn't sure which topic this comes under.

My client has a Lexmark 3500 / 4500 series printer. His computer had a virus, which I god rid of, but now the printer won't work. I have tried everything:

Removing it completely and following the setup instuctions again
Tried to print from Word, Notepad and the Web, also tried printing a test page
However, nothing is in the print queue
But when you ask it to print, the printer icon comes up for about 2 secs and then goes away again.
It is connected to USB001 (I tried LPT1 - didn't work)
Nothing reported to be wrong in Device Manager?

Any suggestions?