What is considered significant when applying for a TCS PhD with major changed I am a Master student on CS. Actually in theory. 
I have a BE in polymer (Chemical Eng stuff), and I struggled somehow to get enrolled in this program. 

I want to apply a TCS  PhD in US. So, what do you people think is important that I get to apply to a PhD ?

Perhaps you may value these following options:


published paper ( I am writing a paper on combinatorics )
strong recommend letter 
a high score on GRE or GRE sub(math or CS ,U Chig  recommends a math sub as far as I know)
Meet some guys who doing recruiting.


Note that I have 2.0/5 GPA on my BE, so this  really upsets me much.

Hope that this problem could help others desiring to do a PhD in TCS.
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.