I tested your command and got the same error:
[user@dom0 ~]$ qvm-template search fedora
=== Name & Summary Matched: fedora ===
fedora-32 : Qubes template for fedora-32
fedora-32-minimal : Qubes template for fedora-32-minimal
fedora-32-xfce : Qubes template for fedora-32-xfce
fedora-33 : Qubes template for fedora-33
fedora-33-minimal : Qubes template for fedora-33-minimal
fedora-33-xfce : Qubes template for fedora-33-xfce
fedora-34 : Qubes template for fedora-34
fedora-34-minimal : Qubes template for fedora-34-minimal
fedora-34-xfce : Qubes template for fedora-34-xfce
fedora-35 : Qubes template for fedora-35
fedora-35-minimal : Qubes template for fedora-35-minimal
fedora-35-xfce : Qubes template for fedora-35-xfce
[user@dom0 ~]$ qvm-template repolist
qubes-templates-itl Qubes Templates repository enabled
[user@dom0 ~]$ qvm-template download fedora-35-minimal
Downloading 'qubes-template-fedora-35-minimal-0:4.0.6-202205081759'...
qubes-template-fedora-35-minimal-0:4.0.6-202205081759: 0%| | 0.00/724M [00:00<Error canonicalizing file: not an RPM package
qubes-template-fedora-35-minimal-0:4.0.6-202205081759: 0%| | 0.00/724M [00:00<
ERROR: [Errno 2] No such file or directory: './tmpxgklz0i4/qubes-template-fedora-35-minimal-0:4.0.6-202205081759.rpm.UNTRUSTED'
The fedora-35 templates aren’t yet available in the stable repository (#6969 not closed and no announce from adw). But in fact, I see the rpms in the templates-itl repository, as you tested there is a problem with these rpms.
So read the adw’s announce for fedora-35 in testing, and if you want to test :
[user@dom0 ~]$ qvm-template --enablerepo qubes-templates-itl-testing download fedora-35-minimal
Downloading 'qubes-template-fedora-35-minimal-0:4.0.6-202205081759'...
qubes-template-fedora-35-minimal-0:4.0.6-202205081759: 100%|▉| 724M/724M [01:05<
[user@dom0 ~]$ sha512sum qubes-template-fedora-35-minimal-0\:4.0.6-202205081759.rpm
a663afd06e9750a9f5d3646e938c1bd36ed98f1c6c04e8f25e3e2d685e72a6cc480c83a40b9e125dcd80b7c2eabe96906e8a562ddad6271508dfaa1d03f5233d qubes-template-fedora-35-minimal-0:4.0.6-202205081759.rpm
See also some qvm-template commands that I tested few months ago.