Well, I'm a bit puzzled by what happens when I attempt to evoke your robots.txt file for openers. Mishandling robots.txt has been known to send Google away. Fast.
Not sure about your "~permalink" structure either.
The 2 sets of category links on the homepage? Duplicate content issues "to the max"? I dunno. Add in the "tag cloud" and it's off to the "we're trying to link spam Google" races - even if that's not your intention.
I'm not a WP SEO expert but I took at quick look at those "elements" and, well, you'll have to figure it out from here. I'm off to fix my own myriad problems.