My husband works for a company based in Connecticut but we live in Texas as he works all over the US but his employer is taking Connecticut state taxes out of his pay?

As a non resident you don’t owe tax to CT. Get the tax withheld by filing a non resident CT return showing no income from CT. 

Q.  My husband works for a company based in Connecticut. We live in Texas and he works all over the US.  Does he owe income tax to the states he actually works in. 

A.  Yes, including CT, if his travels occasionally take him there. 

See:  http://money.cnn.com/2013/06/28/pf/taxes/business-traveler-tax-threat/  The article suggests that many people don't bother to pay tax to those other states.  But, if you live in a state without an income tax (e.g. FL or TX), it’s more likely you should file in the work states. You can't use the "it all comes out even" rationale for not filing.

This is the general rule: The income is work state (WS) source income since it was earned there. Resident States (RS) tax all their resident's income, regardless of where earned. You will file a non-resident tax return for the WS and report the WS income. You will file a full year resident return for the RS, reporting all your income. The RS will give you a credit, or partial credit for any tax paid to the WS. Living in a   a state without an income tax does not get you out of paying state tax to the states you worked in. 

For state filing requirements, the WS does not, usually, go by what you earned in their state but by your total income . For example, if WS has a $10,000 filing requirement and your total income for the year was $15,000; you would be required to file even though you may have had only had $300 of income in that state. But if your total income was $9,000 you would not need to file.

State Filing Requirements: https://ttlc.intuit.com/questions/2903200-do-i-need-to-file-a-state-return