jecasc - 3:08 pm on Nov 23, 2010 (gmt 0)
I don't think this is an issue that can be resolved here. Without looking at the website, the domain and the SERPS it is not possible to tell wether the problems you encounter are a result of malicious intent or the result of pulling the plug on SEO work at the wrong time. Maybe changes had already been made for better ranking which now take effect but do not benefit your website since the contract has been canceled. However it looks to me like the SEO companies intention was to make the SEO work in a way which would have made you dependend on them forever - which may not be illegal but is pretty unprofessional.
So pay another SEO expert to have a look and then decide what steps you should take with Google and if legal actions should be taken as well. If they changed the information in your Google Webmaster Tools account after the contract had been canceled this might even be a case for the police.