I have multiple Template Messages each template associated with workflow and everything is working fine, then I added a new template I found that Template Category options has changed, before I was selecting "Alert Update" but now this option is not available so I chose "Utility".

However, the template that have "Utility" as Category is not working on workflows 

Error shown: