We have not upgraded to that service pack yet, but I did recently report a bug where the history report isn't reporting changes to job history. Of course it's not a bug and I was asked to vote on an idea in the idea Bank.
We are on SP27 and haven't had any problems. It's slow, but it runs and produces results.
Side note… in our staging environment we can't even test the history report because I recently disabled all auditing on all tables.
No auditing = no history report.
We've upgraded to SP28 and this report is running correctly. Same as Nolan's findings - it's slow.