I also want to add that I tested running the services under the local system account (just to test, I know this isn't an option) to see if the job would still fail and it did. Same error. So it's not just when creating maintenance plans under the sql agent account but also as local system and local system has sysadmin privs as well.

Executed as user: *******\SYSTEM. Microsoft (R) SQL Server Execute Package Utility Version 10.0.4000.0 for 64-bit Copyright (C) Microsoft Corp 1984-2005. All rights reserved. Started: 7:40:54 AM Error: 2012-10-23 07:41:00.74 Code: 0xC00291EC Source: {2A18DE07-1322-40AC-AA95-9F41C2FA8ABD} Execute SQL Task Description: Failed to acquire connection "Local server connection". Connection may not be configured correctly or you may not have the right permissions on this connection. End Error Warning: 2012-10-23 07:41:00.74 Code: 0x80019002 Source: OnPreExecute Description: SSIS Warning Code DTS_W_MAXIMUMERRORCOUNTREACHED. The Execution method succeeded, but the number of errors raised (1) reached the maximum allowed (1); resulting in failure. This occurs when the number of errors reaches the number specified in MaximumErrorCount. Change the MaximumErrorCount or fix the errors. End Warning Error: 2012-10-23 07:41:01.25 Code: 0xC0024104 Source: Check Database Integrity Task Description: The Execute method on the task returned error code 0x80131604 (Exception has been thrown by the target of an invocation.). The Execute method must succeed, and indicate the result using an "out" parameter. End Error Error: 2012-10-23 07:41:01.33 Code: 0xC0024104 Source: {AB2FE0CE-1CA4-4E16-9FC0-9172D601D902} Description: The Execute method on the task returned error code 0x80131604 (Exception has been thrown by the target of an invocation.). The Execute method must succeed, and indicate the result using an "out" parameter. End Error Warning: 2012-10-23 07:41:01.33 Code: 0x80019002 Source: OnPostExecute Description: SSIS Warning Code DTS_W_MAXIMUMERRORCOUNTREACHED. The Execution method succeeded, but the number of errors raised (2) reached the maximum allowed (1); resulting in failure. This occurs when the number of errors reaches the number specified in MaximumErrorCount. Change the MaximumErrorCount or fix the errors. End Warning DTExec: The package execution returned DTSER_FAILURE (1). Started: 7:40:54 AM Finished: 7:41:01 AM Elapsed: 6.688 seconds. The package execution failed. The step failed.