I was considering the Marantz VQ2400 upconverter for my setup, but in light of your bad experience, may hold off. Was it the above model you were using, or an integrated upconverter on a marantz receiver?
I am using an Onkyo TX-NR900 receiver, which upconverts composite to s-video. I understand that the new Onkyo models (like the 901, 801, etc.) and the new Denons upconvert s-video to component as well.