I seem to have fixed this problem on my end by adding the following code to "modules/authorizeaim/validation.php:
'x_city' => Tools::safeOutput($invoiceAddress->city),
'x_state' => Tools::safeOutput($invoiceAddress->id_state),
Note "$invoiceAddress->id_state", you can't use "$invoiceAddress->state" becuase "state" does not exist in the database. This will send authorize.net the state id. I don't think authorize.net uses this information but it is a filler to send them and it fixes my problem.
I just did this on a new install of prestashop 1.4.9 but I am curious to know if this works for previous versions as well.