What worked for me (for customers that are not signed in) was to enable the 'country' field, too, alongside the state and zip fields. However, I didn't really want that field, since I don't ship internationally yet. So, I set it manually by adding:
define('STORE_COUNTRY','223');
to catalog/includes/languages/english/modules/shipping_estimator.php
and then disabled the country option again in the admin. Probably a crude workaround, but it seems to work so far.
Note: I am using Steve Fatula's Fedex_Direct_2.04-CVS as my shipping module.