Just a follow up. I have taken my printer into work and tested it on a Windows XP machine. It is printing black fine. Therefore the problem is Linux related and not hardware. Any ideas?