Comment 2 for bug 786048

Looks like a problem with the hpcups driver: prnt/hpcups/Pcl3Gui.cpp 75: Requested resolution not supported with requested printmodeprnt/hpcups/HPCupsFilter.cpp 420: m_Job initialization failed with error = 25

Can you try changing the driver to "hpijs" in System > Administration > Printing (system-config-printer):
Right-click your printer > Properties > Make and Model > Change ...
Does it print grayscale now?