My question is that what would happen to the transaction fees submitted by the user in this case ? Would it also be returned?
Yep, it would for sure.
Why does this occur ?
A transaction is basically rejected either 'coz of low fee or 'coz of dust output. Each & every transaction gets their priority in the blockchain network. There 're a bundle(bunch) of unconfirmed transactions waiting for the confirmation ->
https://blockchain.info/unconfirmed-transactions . Basically, you've to spend more fee to get higher priority in the list & you'll get added to the next block. Dust outputs 're normally created by poor ponzi/gambling sites which ultimately results in the rejection of the transaction.