I finally got this to work. I'm leaving my solution here in case others have a similar issue.
Basically I tried repairing my VS using the Microsoft ASP.NET and Web Tools 2013.1 (I got it from here Microsoft Web Tools download page). However, it didn't solve the problem for me. What did solve it was copying the file Microsoft.Web.XmlTransforms.dll from another machine at the location
C:\Program Files (x86)\MSBuild\Microsoft\VisualStudio\v11.0\Web
Somehow, mine was missing from there (I got it from another computer with the same .NET version and pasted it there) and now the publish works fine.