I got it working finally!! It might help somebody who might be stuck just like me.
The mistake I was doing was I was entering the GUID generated by the tool in UpperCase while it has to be put in "LowerCase". The GUID Generator tool in Visual Studio 2012 generates a GUID something like this: "AAB123-xxxx-xxxx-xxxxxxx" while what the WMAppManifest.xml file takes is: "aab123-xxxx-xxxx-xxxxxxx".
So the steps to change GUID of any project is as follows:
- Go to www.guidgen.com
- Copy the GUID.
- Open Assembly Information and paste it in the GUID field (in lowercase only).
- Open WMAppManifest.xml file and paste it again in the productID field (again in lowercase only)
- Rebuild and deploy the solution.