新品のHL-L8360CDWを購入直後、薄汚れたテストプリントが出力されます

改善しないようであれば、非常に残念ですが、初期不良の可能性が非常に高いと存じます。購入後1年以内でしたらメーカー保証を受けられますので、初期不良として購入店舗またはメーカーコールセンターにお問い合わせしてみてはいかがでしょうか？

その設置されたトナーがどういった保管状態だったか不明ですので不安ですね。
純正品でも大容量トナーだと不具合が出るケースが散見されます。
吸湿によりトナーが均等に吐出されていないのではないか確認されても良いかもしれません。
一旦トナーを抜き出し、トンットンッと塊をほぐし、均等にする感じで振ってみてください。
もし、少しでも改善するようでしたらトナーが原因です。
交換されてすぐでしたら、トナーやドラムの初期不良も考えられます。

あととりあえず、内部の清掃をしてみてはいかがでしょうか。
・LEDヘッドの清掃(あれば)
・コロナワイヤーのクリーニング
・ドラムユニットの清掃
・給紙トレイの清掃
・給紙ローラーの清掃
・ファームウェアを更新
・ドライバーの再インストール
・トナーの交換
・ドラムの交換
下記で改善しないのであれば定着ユニットの可能性がありますので修理依頼ですかね…

【レーザー プリンター】印刷が薄い・かすれる(モノクロレーザープリンター・複合機)
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10246

【レーザー プリンター】印刷が薄い・かすれる(カラーレーザープリンター・複合機)
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10247

【レーザー プリンター】印刷の色合いがおかしい(カラーレーザープリンター・複合機)
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10248

【レーザー プリンター】印刷すると横線が入る
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10249

【レーザー プリンター】印刷すると黒や色つきの縦線が入る
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10250

【レーザー プリンター】印刷すると白い縦線が入る
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10251

【レーザー プリンター】印刷すると点々がつく
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10252

【レーザー プリンター】印刷結果を指でこすると、汚れます
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10253

【レーザー プリンター】印刷面が汚れます
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/10254

【レーザー プリンター】お困りごとナビ　レーザープリンター・複合機印字結果が良くない
↓↓↓↓↓
https://faq.brother.co.jp/app/answers/detail/a_id/13071

https://support.brother.co.jp/j/b/producttop.aspx?c=jp&lang=ja&prod=hll8360cdw
こちらですか。

書かれている内容だと初期不良が疑われます。一度購入先に連絡を入れましょう。初期不良と判断されれば交換となるかと。

初期不良として購入店に相談してみてください