Will I need to do full backup again when I change encryption password?

I would have said the opposite. After changing the password your job won't need an active full backup. The next incremental uses the new password, for existing files the old password is still needed. As long as you don't create a new full backup, you will need both passwords for recovery. At least this is what I experienced  so far and also the helpcenter says the same:

If you change the password for the already encrypted job, during the next job session Veeam Backup & Replication will create a new incremental backup file. The created backup file and subsequent backup files in the backup chain will be encrypted with the new password.

Maybe you can share your results here in your post.