Hi,
This is something that confused me at first too. When you switch the template of an appVM, the menus can't automatically update. Although Debian and Fedora both have gnome-terminal, they are actually invoked slightly differently from the menu (as you can see in ~/.local/share/applications in dom0).
What you need to do is open "Add more shortcuts" for the appVM after changing the template. It will then show the new applications, including the terminal, and let you add them.
Daniel