I updated cups-driver-gutenprint to version 5.2.7-2 which solved the
problem, i.e. the gray colours are now placed correctly. Unfortunately
it also created another problem, which is that the printings look pale,
maybe the dark black ink is missing now. Also I updated cups package
to version 1.4.7-1 but that didn't change anything about the output, just
had to start CUPS server manually.
If you tweaked any settings that got carried over to 5.2.7 e.g.
black density adjustments etc. in the CUPS printer settings, that
could be a possibility. Replacing the PPD file will reset to the
defaults (modify printer on the web page). If this doesn't do the
trick, you could try increasing the black density, but this would
imply the printer has bad defaults, in which case the upstream
mailing list is the best place to ask for how to correct that.