They're beginning to become too soft.. I find that the object I place my focus point on is blurred but something else, somewhere else in the picture is in focus.
So the problem isn't soft images, it's misfocusing. I assume that you're manually selecting the AF point - if you're using automatic (61 pt) AF point selection, the camera will focus on the nearest object under an AF point - it has no way to know what you think is the right subject.
One store was able to narrow the problem down to the 24-70mm Lens I was using, also brought alongside the 5D back in April, and told me I need to recalibrate it. ...I'm starting to think the camera is the problem.
If so, is there any way I can fix this?
It seems most likely that you need to do an AF Microadjustment (probably for many of your lenses, the problem is just most evident on a particular lens). The problem you describe is the classic presentation of a lens and camera being mis-matched for AF accuracy, the problem which AFMA is designed to correct. Here's a tutorial on AFMA that I wrote up, including a DIY option. Currently, I use Reikan FoCal software to do my AMFAs.