That is definitely an error related to having the wrong transaction key.... generating a new transaction key and using it on the site is usually the correct solution. I'd try doing that again, maybe there was a typo?
If you can't figure it out, we could help in a premier support ticket and walk through that process with you making sure there are no mistakes made.