インク交換後、１回も印刷できず、インク終了

https://support.brother.co.jp/j/b/producttop.aspx?c=jp&lang=ja&prod=mfcj5630cdw
こちらですね。他の方が回答されていますが

本製品からプリントヘッドのクリーニングをする
https://support.brother.co.jp/j/s/support/html/mfc5630cdwa_jpn/doc/manual/index.html#GUID-09F6FFB7-C265-4C70-9CC7-2B2F3C37FEC3_375
ヘッドクリーニングを何回も行うと大量にインクを消費してインクカートリッジを交換する必要が出てきます。

＞カートリッジ交換後、１枚も印刷することなく、新品のMカートリッジがインク切れなどはありえますか？

ありえます。ヘッドクリーニングは１回行うと、大量のインクを放出廃棄します。

大量のインクを一気に排出する「勢い」を用いて、詰まったインクカスを取り除くのがクリーニング動作なのです。

１回のクリーニングで、画像数百枚を印刷できる量のインクが捨て去られます。

ですので、クリーニングを５～６回繰り返すだけで、インクタンクが空になる可能性があります。

目詰まりがひどく、目詰まり解消のためのヘッドクリーニングを何度も行うと目詰まり次第ではそのような事になります。
ヘッドクリーニングとはインクを噴き出して行っているのですから・・・
また、目詰まりがもっとひどい場合はインク1つだけでは済まない事もあります。