I had a similar problem running Zen Cart 1.51 and TaxCloud version: 1.5.2b_for_zc151

In admin my configuration for Always show State as pulldown is set to true.

I fixed the issue by writing a code in includes/modules/TaxCloud/func.taxcloud.php to convert the state name to a 2 char code before passing it to TaxCloud.

I made this change in 12/2013 and the store has functioned fine since then.

It did make me wonder how TaxCloud without this fix could be working for others - maybe there's something odd with my configuration