But when we lock UTXO with CHECKLOCKTIMEVERIFY, we have to set nLocktime of a transaction in which UTXO will be referenced as input greater than the CLTV locktime of the UTXO, right?
Correct, the nLocktime of the transaction that "spends" the CLTV UTXO must be greater than or equal to the original CLTV locktime.
My question is, can we relay the above transaction immediately?
No.
OR we have to wait for nLocktime to elapse due to the reason mentioned in first line?
Yes, as you have deduced, you must wait for the CLTV Locktime to have passed before the "spending" transaction will be considered as valid...
refer:
Since a transaction may only be included in a valid block if its nLockTime is in the past, this ensures the CLTV-based timelock has expired before the transaction may be included in a valid block.