Just posting the solution so no someone else suffers the way I did.
Twitter updated the API and added an option named auto_populate_reply_metadata
All you need to do is set that to true, and the leave the rest as should be. Here is a sample:
api.update_status(status="your reply", in_reply_to_status_id = tweetid , auto_populate_reply_metadata=True)
Also, the status_id is the long set of digits at the end of the tweet URL. Good Luck!