Updated 12/20/10 2:59 pm: There is now a correction for this — see comments below.
There are reported problems associated with the Verify command in QuickBooks if you are running under the R4 update. There are posts in the Intuit Community about this problem in Enterprise and Pro/Premier editions.
Charlie Russell wrote about this and advises against installing the R4 update at this time. I agree.
There are a few reports of Intuit level 2 support having a fix. But perhaps the best approach for now is holding off on installing the R4 update, and holding out for R5 (whenever that comes out.)
This is a good example of the advantage of NOT configuring QuickBooks for auto-update. As with all software updates, there is always the possibility in a new release of several bugs being fixed, but a new bug being introduced. There is some wisdom to waiting a few weeks before installing updates, in case there are any serious unanticipated issues with a new update.