I got a later version than that kb specifies and still have a problem with checkdb and same error.

Microsoft SQL Server 2005 - 9.00.3282.00 (X64) Aug 5 2008 00:48:00 Copyright (c) 1988-2005 Microsoft Corporation Enterprise Edition (64-bit) on Windows NT 5.2 (Build 3790: Service Pack 2)