Thank you Siva. I had seen that KB before I posted but didn't think it applied for 2 reasons. One, I do not have Snapshot Isolation enabled on this DB. Secondly, the hot fix was supposed to be included with SP2. Since I'm on SP3 I didn't think it applied here.

I think Lee hit the nail on the head. It's better to use TSQL to do the maintenance than using the built-in SSIS-based maintenance tasks.

For anyone who may stumble across this later, try recreating the problem step first. If that works, great! If not, try recreating it using TSQL instead, mine has been working consistently since I converted it to plain TSQL.