Just recreated the step and confirmed it works by running the SQL Agent job. A couple of things to note:

1) This plan is only being executed on a single database. There are only 8 user DBs on the server and not all of them have maintenance plans. This particular plan is only executing against 1 user database.

2) I recreated the step by deleting the original step and adding a new one. Instead of using the built in "Check Database Integrity" plan task, I created an Execute SQL task and out the following in it: DBCC CheckDB ('MyDatabase') WITH No_INFOMSGS, ALL_ERRORMSGS. Obviously, replace MyDatabase with your actual database name. Assigned this task the same schedule as the one I deleted.

3) Ran the SQL Agent job. Execution was successful and the duration was about the same as before when the task was succeeding.

I'm pretty stumped on this one but since I found a workaround I'm not that concerned. Don't think it's worth calling MS on it either since the solution works. If anyone has anything else to add I'm all ears.