The site is now moved to a faster network and the counter module on the site has been disabled.
That module was practically killing mysql and causing the site to load slow. Examining it, we found that it was counting all the rows in the mysql tables on EACH page load. Bah
After a lot of analysis, we found the module that was the culprit. It has been thrown away.
Enjoy the fast site:-)