I ran
tail /var/log/cups/error_log
after a failed print and noticed this line a few lines before the foomatic-rip failed
error
bash: c2050: command not found
So I tried these commands:
$ c2050
The program 'c2050' is currently not installed. You can install it by typing:
sudo apt-get install printer-driver-c2050
$ sudo apt-get install printer-driver-c2050
After this the printer started printing but was printing garbage. So I first I rebooted the printer and then I removed and re-added the printer. I did it the hard way but you can try the easy way through System Settings first. Anyway, in my case first I added the driver suggested on http://www.openprinting.org/printer/Lexmark/Lexmark-CX310dn. I downloaded the deb file and installed it with
sudo dpkg --install openprinting-ppds-postscript-lexmark_20140829-1lsb3.2_all.deb
and then I visited the CUPs interface and added the printer.
Case solved.