TheMadScientist - 1:55 am on Feb 12, 2010 (gmt 0)

Yeah, one thing to look at here might be the little technicalities of the redirect, possibly not leaving the old site, but arriving at the new one. IOW redirecting to http://example.com/ rather than http://www.example.com/ or http://www.example.com rather than http://www.example.com/ the former will initiate a second redirect if there is www canonicalization in place on the new domain and the latter will result in a second redirect from http://www.example.com to http://www.example.com/.

Also, did you redirect page to page or did you consolidate on the root or certain pages on the new site? IOW when you say you redirected all the pages do you mean you redirected each individual page to a corresponding URL on the new domain name?

3rd Had the new domain name previously been used? I'm guessing it had since you did a reinclusion request, but did you look at the history via archive.org or anything to see what type of content (or spam) it previously hosted? I know I remember reading here somewhere MC (I think) at a PubCon (I think) advised to NOT EVER bother to buy a banned domain, because it was very difficult (next to impossible) to get it back in the results, and I think similar thinking applies to buying penalized domains. Did you buy one of those type of domain and redirect there?

ADDED: Sorry, we've all forgotten our manners, except tedster...
I did anyway. Welcome to WebmasterWorld!