Unable to Create Azure Resource Manager Project

I have just installed Visual Studio 2015 Enterprise Update 3 along with Azure SDK for Visual Studio 2015 and Azure PowerShell Tools.

When I try to create a new project under Visual C#|Windows|Cloud|Azure Resource Group I get the following error after selecting a template and during the project creation.

---------------------------
Microsoft Visual Studio
---------------------------
The system cannot find the file specified. (Exception from HRESULT: 0x80070002)
---------------------------
OK   
---------------------------

I have re-installed Visual Studio and the Azure SDK but the problem persists. I have also tried a number of devenv.exe command line options to clear cache and reset templates but nothing works.

Here is what I did.

Go to the control panel and uninstall all Visual Studio components and sub-components. Then remove all old SDK's. Then reinstall everything.