This isn't a new problem. How often do we see M$ release a service pack (containing updates and fixes) which all too often breaks something else.
In this case, SharePoint Search. And in this case it's a reccurring problem, this particular issue happened with the release of SP1 for MOSS. So the big question is, why M$ havn't learned from the past problem and fixed it?
Anyway, I digress.
Fortunately, since this isn't a new problem there are already documented solutions to it, such as this one from Kindler Chase: http://www.raregrooverider.com/post/2008/02/SharePoint-Services-Search-Error-Event-ID-2424.aspx
And this from Pat McGown: http://blogs.microlinkllc.com/pmcgown/archive/2008/11/07/moss-search-access-denied-event-id-2436.aspx
In my particular case it was the latter resolution with disabling the loopback check which fixed it.