Sometimes you may know about the blacklisting before Support does. That's why I suggested that the first step is to report this to Support. They will investigate to find the source of the problem on the server, then they will contact the blacklists to request removal. Support does not have the power to directly remove the IP from the blacklist. Support must request removal from each list, after first suspending the problem account.
No, it is not abnormal. It is undesireable, but not abnormal on shared hosting. Unfortunately, blacklisting happens periodically for shared servers. Likely someone on your server was sending spam, or had a high-volume mailer sending uncontrolled amounts of mail in a short time. Because all senders on a shared server share the same mail server IP, when that spammer gets blacklisted so does everyone else on the server.
That's why I suggested that you tell your clients to set their ISP's SMTP server for outgoing mail, thus bypassing any blacklist issues with the WHB server. IMHO, it's better to have your clients always use their ISP's SMTP server for outgoing mail.
I am not WHB staff and I am not paid.
I provide help in these forums on my own time.