What is considered significant when applying for a TCS PhD with major changed
If you're currently a masters student in CS, then a lot of your 'switched major' issues have already gone away. the main concern in applying for a Ph.D in TCS is if you have sufficient mathematical background, as well as background in algorithms. If your MS program experience can demonstrate this, and you also can demonstrate mathematical expertise via your paper in combinatorics, then that concern goes away. 

But admissions decisions are multivariate and stochastic. Maybe the right question is whether you have the right background to succeed, and there are answers regarding what constitutes the right background (on mathematical background). Also see this on how to prepare for a TCS advanced degree.