Is there any update on this issue? We are planning to replace app icons for the app which is already in App Store.

Apple does not have any restrictions on this. The only rule is that the version and build numbers must be greater than the current version when submitting an update. You can increment it however you want.