I cannot fully reporoduce your issue.
I need more information, see
http://en.opensuse.org/SDB:How_to_Report_a_Printing_Issue

I get same error messages in /var/log/cups/error_log
but printing the CUPS test page works for me
on my HP LaserJet 1200 printer both in PostScript mode
and in PCL5e mode.

What printer driver do you use for your Samsung SCX-4833 printer?

According to
http://www.openprinting.org/printer/Samsung/Samsung-SCX-483x_5x3x
it seems the Samsung SCX-4833 is a PostScript printer.
If yes, what PPD file do you use for it?
Please attach your PPD file /etc/cups/ppd/<queue_name>.ppd
as MIME type "text/plain" to this bug.

Regarding the CUPS fonts:

In the cups package /usr/share/cups/fonts/ is a symlink
that points to /usr/share/ghostscript/fonts so that the
Ghostscript fonts should be used but the Ghostscript fonts
do not contain "Monospace*" font files.

Does it work for you when you copy the CUPS upstream "Monospace*"
font files into the /usr/share/ghostscript/fonts directory?

I think the issue happens only when printing the special
CUPS test page /usr/share/cups/data/testprint
which is a special kind of CUPS banner page.

It seems the CUPS test page printing has a hard requirement
to use the CUPS upstream "Monospace*" font files.
Perhaps also CUPS banner pages are affected.

Does printing PostScript and plain (ASCII) text work for you?

E.g. do the following commands print for you?
echo Hello | lp -d <queue_name>
echo A4 | a2ps -1 -M A4 -o- | lp -d <queue_name>
see
http://en.opensuse.org/SDB:How_to_Report_a_Printing_Issue

Created attachment 573642 [details]
Samsung SCX-4833 PPD file used

> What printer driver do you use for your Samsung SCX-4833 printer?
Printer is connected through ethernet. It is connected to CUPS using JetDirect backend:
DeviceURI socket://192.168.0.14
Driver is selected from Samsung Unified Driver installation:
*Product: "(Samsung SCX-483x 5x3x Series)"

> Does it work for you when you copy the CUPS upstream "Monospace*" font files into the /usr/share/ghostscript/fonts directory?
Yes, I had to add the files to the directory to make printer print a test page. And after addition, all jobs are printed Ok.

> E.g. do the following commands print for you?
echo Hello | lp -d <queue_name>
echo A4 | a2ps -1 -M A4 -o- | lp -d <queue_name>

Yes, these commands perform printing without error (without Monospace* files).

Many thanks for your information.

I think now I know what went wrong for your particular PostScript printer:

Without the Monospace* files in /usr/share/ghostscript/fonts
CUPS makes PostScript without those fonts embedded but
those fonts are used in the PostScript.

To see that, set up a testing print queue that prints into a file
and inspect the printout in that file.

As root do:
1.)
Add in /etc/cups/cupsd.conf the line "FileDevice yes"
and restart the cupsd.
Note the security information regarding "FileDevice" at
http://www.cups.org/documentation.php/doc-1.5/ref-cupsd-conf.html
2.)
# lpadmin -p testq -v file:///tmp/testq.out \
  -P /usr/share/cups/model/Postscript.ppd.gz -E

Now print the CUPS test page with and without the Monospace* files
in /usr/share/ghostscript/fonts and compare the printouts in
/tmp/testq.out

Usually a PostScript interpreter uses a fallback font when
a used font is missing.

For example when you run Ghostscript via "gs -r50 /tmp/testq.out"
without the Monospace* files in /usr/share/ghostscript/fonts
you get Ghostscript messages like:
Substituting font Courier for Monospace.
Substituting font Courier-Bold for Monospace-Bold.
Substituting font Courier-Oblique for Monospace-Oblique.
Substituting font Courier-BoldOblique for Monospace-BoldOblique.

This is why my HP LaserJet 1200 prints the CUPS test page in PCL mode
because then Ghostscript is used as PostScript interpreter and
when my HP LaserJet 1200 prints the CUPS test page in PostScript mode
it is the printer's built-in PostScript interpreter that
uses a fallback font when a used font is missing.

But it seems your Samsung SCX-483x 5x3x Series printer fails
in this case. To verify this you could do the following:

Usually in a PostScript printer you can you switch on
that it prints out PostScript errors if it fails
to process PostScript so that you get a PostScript error
printed in such cases.

Unfortunately those PostScript error printouts are usually disabled
by default so that the user is not informed what went wrong.

Of course it saves a lot of paper (and money) when the one sheet
with the PostScript error is not printed and apparently it costs
nothing when then users need a lot of time to find out why
a particular document does not print... ;-)

I do not say that the typcial PostScript error printout text
is meaningful for normal users but at least they would know
their printer somehow does not like the particular document.

Submitted fixed cups package to its OBS devel project "Printing"
together with a fix for bnc#857372 via submitrequest 213204
and forwarded this to openSUSE:Factory as submitrequest 213206.

FYI:
The matching RPM changelog entry is:
--------------------------------------------------------------------------
- Do no longer use the Ghostscript fonts for CUPS. Instead be
  in compliance with upstream and use CUPS' own Monospace fonts
  in /usr/share/cups/fonts because those fonts are hardcoded
  used by the CUPS filters bannertops (for CUPS banner pages and
  the CUPS test page that is a special kind of banner page)
  and texttops (when printing plain text files). Without CUPS'
  own Monospace fonts bannertops and texttops create PostScript
  that uses those fonts but without those fonts embedded which
  results that PostScript interpreters use a (different) fallback
  font or fail to print for some PostScript printers (bnc#856731).
--------------------------------------------------------------------------

This is an autogenerated message for OBS integration:
This bug (856731) was mentioned in
https://build.opensuse.org/request/show/213206 Factory / cups

The new cups package cannot be installed without that RPM conflict:
---------------------------------------------------------------------------
file /usr/share/cups/fonts from install of cups-1.5.4-131.1.i586
 conflicts with file from package cups-1.5.4-12.1.3.i5
---------------------------------------------------------------------------

It seems RPM has an issue when the installed symbolic link
  /usr/share/cups/fonts -> ../ghostscript/fonts
should be replaced by a real directory with files
  /usr/share/cups/fonts
  /usr/share/cups/fonts/Monospace
  /usr/share/cups/fonts/Monospace-Bold
  /usr/share/cups/fonts/Monospace-BoldOblique
  /usr/share/cups/fonts/Monospace-Oblique

I know that it is not possible with RPM to exchange
an installed directory by a symbolic link (even
RPM scriptlets do not help), see the mail thread
"RPM how to change a directory to a link" in particular
http://lists.opensuse.org/opensuse-packaging/2011-02/msg00034.html
http://lists.opensuse.org/opensuse-packaging/2011-02/msg00079.html

Now it seems the other way round has also RPM issues...

Even if I fond a way how to replace a symbolic link by a directory
in RPM, this would not help because then theer would be no way back
to re-replace that directory by the symbolic link before.

In other words:
If cups-<new.version> would replace the symbolic link
/usr/share/cups/fonts -> ../ghostscript/fonts
by the directory /usr/share/cups/fonts/ with CUPS' own
Monospace font files therein,
then cups-<old.version> could no longer be installed with RPM
because is not possible with RPM to exchange an installed
directory by a symbolic link.

This means those symbolic link
/usr/share/cups/fonts -> ../ghostscript/fonts
is an evil piece of sticky crap that I inherited from ancient times
when there was the general opinion it would be a great idea
to deviate from CUPS upstream and save some disk space and
do not install CUPS' own fonts in CUPS' own font directory :-(

As far as I see it seems that /usr/share/cups/fonts
must stay forever as a symbolic link.

As far as I see currently the only way out is to install
CUPS' own fonts in an artificial surrogate directory like
/usr/share/cups/CUPSfonts and have the symbolic link
/usr/share/cups/fonts -> /usr/share/cups/CUPSfonts

I really really hate it when packages are not made in
full compliance with upstream. Sooner or later but always
this leads to nothing else but overcomplicated mess
and bugs and annoyance for everybody - cf.
https://bugzilla.novell.com/show_bug.cgi?id=735824#c36

Submitted fixed fixed cups package to its OBS devel
project "Printing" via submitrequest 213436 and forwarded this
to openSUSE:Factory as submitrequest 213437.

This is an autogenerated message for OBS integration:
This bug (856731) was mentioned in
https://build.opensuse.org/request/show/213437 Factory / cups

Please look at sr#213875.

Sascha Peilicke,
I will check it when I finished working on my security bugs...

On a first glance I think in
http://paste.opensuse.org/32487394
your "zypper in -f" is like "rpm -UHV --force" and that "force"
will ignore the RPM conflict in my comment#6 above.

Sascha Peilicke,
please use plain /bin/rpm to really see what RPM does.
Higher level package management tools (like zypper or YaST)
may not show all RPM issues in their user interfaces.
Does it also work for you using plain rpm (without "force")?

Why do I care so much about plain RPM?
Once bitten, twice shy:
I like to be 100% safe from any RPM package upgrade issues.
I had package upgrade issues in the past for SLE10 or SLE11
for the HPLIP package and got then very urgent critical bugs
because the whole SLE installation basically stopped
because of that HPLIP package upgrade issues.

A typo in comment#12: I meant "rpm -Uhv --force"

home:saschpe:branches:Printing/cups does not work (as in comment#6)
in contrast Printing/cups does work:

On my openSUSE 13.1 system:
----------------------------------------------------------------------------
# ls -l /usr/share/cups/fonts
lrwxrwxrwx 1 root root ... /usr/share/cups/fonts -> ../ghostscript/fonts

# osc getbinaries home:saschpe:branches:Printing cups openSUSE_13.1 i586
cups-1.5.4-138.1.i586.rpm
...

# rpm -Uhv binaries/cups-1.5.4-138.1.i586.rpm \
 binaries/cups-client-1.5.4-138.1.i586.rpm \
 binaries/cups-libs-1.5.4-138.1.i586.rpm
warning: binaries/cups-1.5.4-138.1.i586.rpm:
 Header V3 RSA/SHA1 Signature, key ID 29b1270e: NOKEY
Preparing...                   ################################# [100%]
        file /usr/share/cups/fonts from install of cups-1.5.4-138.1.i586
        conflicts with file from package cups-1.5.4-12.1.3.i586

# osc getbinaries Printing cups openSUSE_13.1 i586
cups-1.5.4-136.1.i586.rpm
...

# rpm -Uhv binaries/cups-1.5.4-136.1.i586.rpm \
 binaries/cups-client-1.5.4-136.1.i586.rpm \
 binaries/cups-libs-1.5.4-136.1.i586.rpm
warning: binaries/cups-1.5.4-136.1.i586.rpm:
 Header V3 DSA/SHA1 Signature, key ID 98c4529d: NOKEY
Preparing...                   ################################# [100%]
Updating / installing...
   1:cups-libs-1.5.4-136.1     ################################# [ 17%]
   2:cups-client-1.5.4-136.1   ################################# [ 33%]
   3:cups-1.5.4-136.1          warning: /etc/cups/cupsd.conf created
                               as /etc/cups/cupsd.conf.rpmnew
                               ################################# [ 50%]
Updating /etc/sysconfig/cups...
Cleaning up / removing...
   4:cups-1.5.4-12.1.3         ################################# [ 67%]
                               redirecting to systemctl try-restart cups
   5:cups-client-1.5.4-12.1.3  ################################# [ 83%]
   6:cups-libs-1.5.4-12.1.3    ################################# [100%]

# ls -l /usr/share/cups/fonts
lrwxrwxrwx 1 root root ... /usr/share/cups/fonts -> CUPSfonts
----------------------------------------------------------------------------

With Printing/cups even the way back "just works":
-----------------------------------------------------------------------------
# rpm -Uhv --oldpackage binaries/cups-1.5.4-12.1.3.i586.rpm \
 binaries/cups-client-1.5.4-12.1.3.i586.rpm \
 binaries/cups-libs-1.5.4-12.1.3.i586.rpm
Preparing...                  ################################# [100%]
Updating / installing...
   1:cups-libs-1.5.4-12.1.3   ################################# [ 17%]
   2:cups-client-1.5.4-12.1.3 ################################# [ 33%]
   3:cups-1.5.4-12.1.3        warning: /etc/cups/cupsd.conf created
                              as /etc/cups/cupsd.conf.rpmnew
                              ################################# [ 50%]
Updating /etc/sysconfig/cups...
Cleaning up / removing...
   4:cups-1.5.4-136.1         ################################# [ 67%]
                              redirecting to systemctl try-restart cups
   5:cups-client-1.5.4-136.1  ################################# [ 83%]
   6:cups-libs-1.5.4-136.1    ################################# [100%]

# ls -l /usr/share/cups/fonts
lrwxrwxrwx 1 root root ... /usr/share/cups/fonts -> ../ghostscript/fonts

# rpm -V cups
S.5....T.  c /etc/cups/cupsd.conf
-----------------------------------------------------------------------------

In contrast with home:saschpe:branches:Printing/cups
First installing it:
-----------------------------------------------------------------------------
# rpm -Uhv --replacefiles binaries/cups-1.5.4-138.1.i586.rpm \
 binaries/cups-client-1.5.4-138.1.i586.rpm \
 binaries/cups-libs-1.5.4-138.1.i586.rpm
warning: binaries/cups-1.5.4-138.1.i586.rpm:
 Header V3 RSA/SHA1 Signature, key ID 29b1270e: NOKEY
Preparing...                   ################################# [100%]
Updating / installing...
   1:cups-libs-1.5.4-138.1     ################################# [ 17%]
   2:cups-client-1.5.4-138.1   ################################# [ 33%]
                               Migrating from Ghostscript fonts
                               to CUPS fonts by removing
                               /usr/share/cups/fonts symlink
   3:cups-1.5.4-138.1          warning: /etc/cups/cupsd.conf created
                               as /etc/cups/cupsd.conf.rpmnew
                               ################################# [ 50%]
Updating /etc/sysconfig/cups...
Cleaning up / removing...
   4:cups-1.5.4-12.1.3         ################################# [ 67%]
                               redirecting to systemctl try-restart cups
   5:cups-client-1.5.4-12.1.3  ################################# [ 83%]
   6:cups-libs-1.5.4-12.1.3    ################################# [100%]

# ls -l /usr/share/cups/fonts
total 688
-r--r--r-- 1 root root 187953 Jan 14 14:11 Monospace
-r--r--r-- 1 root root 159532 Jan 14 14:11 Monospace-Bold
-r--r--r-- 1 root root 166263 Jan 14 14:11 Monospace-BoldOblique
-r--r--r-- 1 root root 185301 Jan 14 14:11 Monospace-Oblique
-----------------------------------------------------------------------------

Then trying to go back to the openSUSE 13.1 GA packages:
-----------------------------------------------------------------------------
# rpm -Uhv --oldpackage binaries/cups-1.5.4-12.1.3.i586.rpm \
 binaries/cups-client-1.5.4-12.1.3.i586.rpm \
 binaries/cups-libs-1.5.4-12.1.3.i586.rpm
Preparing...                  ################################# [100%]
        file /usr/share/cups/fonts from install of cups-1.5.4-12.1.3.i586
        conflicts with file from package cups-1.5.4-138.1.i586

# rpm -Uhv --oldpackage --replacefiles \
  binaries/cups-1.5.4-12.1.3.i586.rpm \
  binaries/cups-client-1.5.4-12.1.3.i586.rpm \
  binaries/cups-libs-1.5.4-12.1.3.i586.rpm
Preparing...                  ################################# [100%]
Updating / installing...
   1:cups-libs-1.5.4-12.1.3   ################################# [ 17%]
   2:cups-client-1.5.4-12.1.3 ################################# [ 33%]
   3:cups-1.5.4-12.1.3        warning: /etc/cups/cupsd.conf created
                              as /etc/cups/cupsd.conf.rpmnew
                              ################################# [ 50%]
error: unpacking of archive failed on file /usr/share/cups/fonts:
  cpio: rename failed - Is a directory
error: cups-1.5.4-12.1.3.i586: install failed
error: cups-1.5.4-138.1.i586: erase skipped
Cleaning up / removing...
   4:cups-client-1.5.4-138.1  ################################# [ 67%]
   5:cups-libs-1.5.4-138.1    ################################# [ 83%]

# rpm -V cups
Unsatisfied dependencies for cups-1.5.4-138.1.i586:
 cups-libs = 1.5.4-138.1 is needed by (installed) cups-1.5.4-138.1.i586
[tons of more failure messages]

# rpm -q cups
cups-1.5.4-138.1.i586
# rpm -q cups-libs
cups-libs-1.5.4-12.1.3.i586
# rpm -q cups-client
cups-client-1.5.4-12.1.3.i586
-----------------------------------------------------------------------------

Now the CUPS packages are messed up.
See cups.spec for explanation why matching release is of importance.

And now there is no way out.

I cannot even fix it by "force" installing Printing/cups
-----------------------------------------------------------------------------
# rpm -Uhv --force binaries/cups-1.5.4-136.1.i586.rpm \
 binaries/cups-client-1.5.4-136.1.i586.rpm \
 binaries/cups-libs-1.5.4-136.1.i586.rpm
warning: binaries/cups-1.5.4-136.1.i586.rpm:
 Header V3 DSA/SHA1 Signature, key ID 98c4529d: NOKEY
Preparing...                  ################################# [100%]
Updating / installing...
   1:cups-libs-1.5.4-136.1    ################################# [ 17%]
   2:cups-client-1.5.4-136.1  ################################# [ 33%]
   3:cups-1.5.4-136.1         ################################# [ 50%]
error: unpacking of archive failed on file /usr/share/cups/fonts:
 cpio: rename failed - Is a directory
error: cups-1.5.4-136.1.i586: install failed
error: cups-1.5.4-138.1.i586: erase skipped
Cleaning up / removing...
   4:cups-client-1.5.4-12.1.3 ################################# [ 67%]
   5:cups-libs-1.5.4-12.1.3   ################################# [ 83%]

# rpm -V cups | head
Unsatisfied dependencies for cups-1.5.4-138.1.i586:
 cups-libs = 1.5.4-138.1 is needed by (installed) cups-1.5.4-138.1.i586
[tons of more failure messages]
-----------------------------------------------------------------------------

Also "force" installing the openSUSE 13.1 GA packages fails in the same way.

I decline sr#213875.

Sure, "rpm -Uhv --force" will ignore the conflict and %pre will fix it. That's the case even with plain "zypper install" http://paste.opensuse.org/14499866. I had to use "install --force" only because of the version downgrade and vendor change. But users / customers will use our update stack (zypper patch / update), never plain "rpm -U", so it's a non-issue IMO.

forgot the needinfo

Sascha Peilicke,
I really would appreciate it if you just trust me and accept
my submitrequest 213437 with my working solution that you declined.
Currently CUPS in openSUSE:Factory is broken as long as
you keep my submitrequest 213437 declined.
Even if we might later find a better solution
CUPS in openSUSE:Factory should be kept working.

Then bring the matter to the attention of the openSUSE review team so that they can decide what's best. I can only repeat that it is not relevant how "rpm -U" behaves, it is not used as such in our update stack. 

So I even provided you with the default solution. Not only does it avoid another deviation from upstream, it is actually fixing the issue. It even tells the user while upgrading if he suffered from it and how it's fixed.

FYI:
Again this issue has to wait because of security issues elsewhere...

*** Bug 859271 has been marked as a duplicate of this bug. ***

I'm guessing a component of this problem is misplaced case sensitivity or case insensitivity. Fc-match monospace should probably not match Monospace. The string monospace is a generic name that is supposed to apply to whatever monospace font family closest to the top of the applicable fontconfig alias list is installed. On my systems that is Droid Sans Mono, with second choice DejaVu Sans Mono in case Droid Sans Mono is not available. Since this bug's purported fix went online, KDE3 is using the Ghostscript font Monospace instead of Droid Sans Mono when monospace is specified, which means not only the wrong font is used, but also the leading/line-height/line-spacing is inappropriate to the contexts in which KDE uses monospace.

CUPS in OBS devel project "Printing" and openSUSE:Factory
and in IBS for SLE12 is fixed as described in comment#8
so that package update also works with plain RPM
which is mandatory for SUSE Linux Enterprise.