They said they think they were breached sometime between April and June. Heartbleed was announced in April. The window was zero to two months, not five.
And it's not that data security is a low priority, it's just that it may not be as high a priority as network availability. This is health care, where problems in communication might affect patient outcomes. "Hey, sysadmin, Doctor Green couldn't respond to his page last night, and the patient died as a result." These are the kinds of arguments that are thrown at the IT departments at every health care provider. Whether or not we consider them rational or valid is irrelevant.
So in that backdrop, we might try to understand that they probably don't just slam in every patch that the vendor has to offer, at least not without a giant process circus. I would guess that they have a patch intake process, where they have to run the patch by some engineering team that evaluates the nature of the patch, and devises some kind of testing plan to execute in their lab environment. They then have to pass it to the testing team who will set up and execute the patch process in the lab, document all their findings, and then turn the patch over to the production network team. They'll put it on their list, and they'll have their own manager who says "whoa, why are you security guys rushing to slam this patch in to my border router? Let's slow down and think about this one."
I could easily see it taking a month in a big, regulated corporate environment.