You should. Or conversely, you can look at this as having dodged a bullet.
On paper, they were willing to commit to multiple years of a presumptively-six-figure salary to you (seriously: an employment agreement is a big financial deal, even if it's legally "at will" -- there's a lot of money on the table) but pulled out because of some fear of bureaucracy and (maybe) a tax increase? That tells me that the commitment they were thinking of putting on paper wasn't worth, heh, the paper.
That's not a loyal employer, basically. If they're willing to cut corners with the State of Florida they'll do it with their own employees too.