From IRS perspective, it doesn't really matter 公司的W-4狀態如何填 as long as enough income tax is witheld at source.
If I were you, I would check "Single" for 公司的 Federal W-4 for 2011, "Married" for 2012. You should be able to get tax refund for 2011 later on.
Make sure you submit ITIN application for your wife when you file 2011 tax return. You should be able to claim as "Married" on form 1040 for 2011.
Not sure about CA tax.