Update:
After spending yet another afternoon trying to fix this, I now have two theories:
1) Bug in CUPS/Foomatic-rip/GhostScript/ICM/ICC/whatever that replicates itself when Linux Distros autoupdate their printer drivers from the net. Thus it doesn't matter if you use an old version or not as it updates itself if the computer is connected to the Internet. I'm too tired right now to give it another try without an internet connection.
I don't think this is a bug in any Samsung printer driver, as I found posts on various forums about the same problem with Canon and HP printers when I googled. It seems related to CUPS and I'm still trying to wrap my head around how CUPS, CUPS filters, Foomatic, colord and GhostScript are all related to one another and where their config files are stored so I can take a look.
2) I took a look at the /var/spool/cups files to see if perhaps colour information wasn't passed on to the printer in the PostScript file. To my surprise, it seems to just pass on image files (jpeg, gif etc) and pdf/ps to the printer directly. Contrary to Windows where the printout is "translated" before being sent to the printer. This leads me to believe that somehow the printer is stuck in monochrome mode and everything being sent directly to it won't print in colour. This doesn't explain though why the demo page printed directly from the printer prints in colour.
Once again, I checked all settings to make sure they are set to "color" wherever possible.
On the plus side, I found the service manual for the printer and there is indeed an option to do a full reset to default settings, I'm saving it as a last resort.
Update 2:
I had an idea and put a .ps file on a USB memory stick, put it in the USB port on the printer and tried printing the file directly, surpassing any existing driver or setting problem. It came out in grayscale.
I'm starting to feel like Jim Carrey's character in the movie Liar Liar when he can't lie but tries in vain to say out loud "this pen is red!". In the end, he's mentally shattered and gives up, crying out "It's blue! The g-d d-mn pen is bluuuuueeee!"
Update 3:
I printed a colour photo I took with my mobile phone, using the Samsung Print Plugin Android app. It came out in colour.
Then I scanned the very same colour photo I just printed and stored it on the memory stick, still in the printer, then printed the picture. It came out in grayscale.
After that, I put the memory stick in the computer just to make sure the image was scanned in colour mode. It was, as a pdf.
I changed the scanner settings to save scanned images as jpeg and scanned the image again to the memory stick and printed it directly from the printer. Once again, grayscale.
Just for the hell of it, I tried the same thing with a Windows Phone and an iPad. Same result: Printing from any of the mobile devices produces a colour print. Scanning the very same image and printing it results in a monochrome print.
Right or wrong, I conclude for now that it's a bug in the printer or firmware and that the Linux driver lacks any kind of workaround that exists in the other drivers or mobile printing apps.
Update 4:
Umm, there is no option anywhere on the printer to change colour/monochrome settings when it comes to printing!?! I checked every menu both from the control panel and from the SyncThru Web Service. You can change Colour on/off/auto when copying or scanning, but not printing? Could it be that it somehow defaulted to monochrome and that there's no way to change it back?