I run into this issue on occasion when I am settling one of my client's personal injury cases. I tell the healthcare provider that they had either a contractual duty (if they are a network provider), or a duty to my client (if they are not a network provider) to follow all necessary steps and time limits to get paid. I tell them that if they fail to do so, they are going to have to "eat their bill."
Keep in mind, this is subject to any co-pays or deductibles which the client would have been responsible for anyway AND the client would've had to provide them their healthcare insurance when they were seen. You can take this position with the healthcare provider. In the meantime, I would contact my healthcare insurance company and get information from them when the bill was submitted and why it was rejected. You may need this case you are sued by the Dr., or the Dr. turns you into a credit reporting agency. Now if the Dr. is a friend or you want to keep seeing the Dr. in the future, I suggest you work out something that you can both live with.