I found the fix for my printing problem – the problem was that I don trust the Fedora printing manager (it didn’t work well for Fedora 7) and tried to use the CUPS web configuration interface. But the only PPD foomatic providesd for this printer uses hpijs which isn’t installed. I used the Fedora printer manager to remove the previous broken setup and create a new one – and it figured it needs to install hpijs and did it for me. Now everything works 🙂