Disabling the contacts and the calendar was one of the first things I tried, without success. That said, I have found the cause of this issue, and a temporary work-around. You can read the full solution here -
http://discussions.apple.com/thread.jspa?threadID=1696689&tstart=0 but in short, the problem was meeting requests still in my inbox. Once I deleted those meeting requests (all of them, accepted, unfulfilled, and pending) my Push started to work properly.