Yes, the algorithm is updated, you're right about that. And something funny happened with googlebot crawling too. Just recently, several people reported that googlebot stopped crawling their websites. For details, see this thread: Googlebot taking a vacation? [webmasterworld.com]
I kind of agree on your advice to Mikey85 that he should wait a bit. Not because I think that PR is the issue, but simply because this looks like something that Google will fix and may even be fixing right now.