Publishing a paper that's already been cited
I think it should do more good than harm. The fact that you have been cited and your results extended means that your paper was relevant, which is a good thing. You definitely need to modify the paper though, not only to acknowledge the citing paper, but because you shouldn't publish a conjecture that is now known to be false.

Disclaimer: although I think the citation should help, this may be quite dependent on the particular reviewer(s) you get. The popularization of arXiv has been relatively recent in the CS field, and at least in many subcommunities the issues that come with it are still subject to debate and the "codes of conduct" are a bit blurry.