I found this article in a forum I subscribe to. I know it is for a C5200N but there may be similarities in the situation.
1.) The printer obviously comes with A LOT of software, right? Make sure that you have uninstalled EVERY piece that comes with it including a.) color managment software b.) drivers in the Add/Remove programs list, c.) services that might be running, d.) Device Manager -->View -->Hidden Devices, e.) delete program file folders after removal, f.) scan the registry for major words like Okidata and executable names . . . save them out and delete the data.
2.) The C5200N is Postscript and PCL6 compatible. Try uninstalling the printer and using a standard Postscript printer (color obviously) and see if it is functional. It might not have all of the bells and whistles with the software, but it will be usuable without wiping the hard drive and reinstalling.
3.) I once had a similar problem with an HP printer. It ended up being a file that HP copied to the system32 folder and failed to remove it during the removal process or rewrite it during the reinstallation process. I finally used a program called FILEMON to watch what files were written during the installation process (i.e. start Filemon . . .start installation . . . stop filemon and look at the result). You can sort the rather long list of files by location so that you can look in out of the way places for files that are possible corrupted and not being removed.http://www.snapfiles.com/get/filemon.html
There is a similar program for registry changes called regmon, but you would get copious results and it might not be useful to you. Here is the link anyway, though. http://www.snapfiles.com/get/regmon.html
I hope this helps.