Please post back and describe exactly how your tax rule is defined in your cart so that we can help to determine why it is not occurring. If you are basing it off of the state what value are you comparing in the tax rule for the state?
The value that you are comparing to needs to be set to the state for the user, if it is not the rule will work correctly. If you are using a remote checkout the user will likely be going to the remote site after the checkout. How do you have yours setup? Do you go from the checkout page to the confirm page before going to the gateways site? If so then you should have a chance to grab the user's state before sending them off to get the tax to show properly.
Along with the details please also post back with any relevant files like the checkout, confirm, and a copy of your cart file from within the WA_eCart folder. Make sure to take out any login or gateway credentials from your checkout pages before posting them here in a zip archive.