Hugene - 8:24 pm on Jul 8, 2010 (gmt 0)
First, in G's very own words, Page Speed is yet just a small factor in the ranking algo. Considering that the algo probably has hundreds of inputs, I really don't think that page speed is actually that important. Also, it will never become that important because of broadband. Back in the 56k days, pages speed did matter to the consumer; now it doesn't so. So why should G really care.
Second, if you still want to go for the Page speed bandwagon, just run Page Speed test in the Firebug firefox add-on. It will tell you your score, and if it is over 70%, your more than OK (I think). Also, it will tell you what you can change. You can gain a lot in the small details, without having to redesign and remove all <tables>. Tables actually don't hurt that much.
Third, flicky, all this is too late for you, but I suggest you got Webmastertools and use the option "Fetch as Googlebot". For your site to have disappeared, it means that googlebot is not seeing it like it used to.
What I mean is: the fact that the <tables> are gone is not that important. What about all the:
*headers (h1, h2...)
*title attributes, alt attributes
*meta data in <head>
*site structure in general
*maybe some content is hidden by CSS?
What I suggest is maybe to get an old browser, like Linx or something, and view your page. Maybe some content is hidden to googlebot by the CSS.
Also, do a HTML validation of your code, maybe there is some error that makes it display incorrectly to googlebot.