I feel your pain, Akuji!
About 1.5 years ago I was in an office that purchased a CLP-500 (against my recommendation of a cheaper HP laser grr). I almost went bald trying to get this printer to play nice (both with Linux and Windows). I cannot remember precisely how I got it working -- and I'm not sure I want to remember

, but you may try finding the .ppd file for the printer. It should be located somewhere under the installation directory for the Samsung driver. Copy that to /etc/cups/ppd/. You can then use the KDE control centre to install a new printer, specifying a specific .ppd file (don't believe this is possible in the CUPS web interface).
It seems the thread over at linuxprinting.org for the CLP-500 has been added to since I last read it, you may find some of the comments there useful.
Good luck (you'll need it!), I'll grep my long-term memory...
Cheers,
odevans