Yes, Greeinify is a task killer essentially, if a glorified one. All apps are 'paused' when sent to the background unless they're actively doing something (if they didn't, you battery would last two hours per charge!). That's where PUSH notifications come in. While the app is not active and is lying dormant in the background, when a message is received, PUSH 'wakes up' the notification process and when you open back the app, it should re-spawn. But if you kill the dormant process with a task manager/killer like Greenify (you could be 'killing' secondary processes you didn't know you needed for BBM), you mess up with the way these apps work.
The running notification is a way for an app to keep all their processes active in the background and prevents them from being terminated by the system. If BBM uses this, then I'm sorry to say but it's not a nicely-coded app. Many messaging apps can achieve this without needing all their processes to be constantly running, and what's more, to have that ugly, constant notification in your notification bar.
Try disabling Greenify for a couple of days and see if that makes a difference.