When I was first building a VM template for Windows 2012, I wanted the base install to be core. I was going to have a deployment option that would kick off a GUI install script during the provisioning if you wanted GUI instead.
I ran into the same problems you did, and I found the same regurgitated series of posts outlining how you just need to point at an updated installation source.
I spent over 2 weeks doing nothing but trying to get this to work. I created WIM files and updated that. I created VHDs and tried to update those, and I used PowerShell to get updates from WSUS using the new cmdlets, in order to automate the process of updating the images.
Bottom line is that it never worked. I could try it with 1 update. And it worked with that. A few more it worked with that. But there were hundreds of updates and somewhere along the way, one update or some combination of updates prevented the transition.
Unfortunately, I eventually just decided to make my template GUI by default, and have a Core option. If you choose core on deployment with my template, then it removes the GUI, and tries to remove all the roles and features that core didn't have (I diffed them to find out). It still doesn't end up as small as core.
But what I did find is that doing it this way has so far always allowed me to go from one of these core machines back to GUI.
What I think is happening
One of the things I noticed when trying to update an installation source, is that not all updates are allowed to be installed offline and this meant it was impossible for me to make an offline installation source that was completely up to date.
I toyed with the idea of having a VM whose sole purpose to be a GUI install that I applied updates to and then made a WIM out of it to use as an install source just for deploying VMs that started as Core but wanted to add a GUI later.
I never got around to it, mostly because it would be a huge pain in the ass for very little benefit; we almost never switch from Core to GUI.
I wish I had better news for you; this issue really irks me. And it's not fixed in 2012 R2 (as you're seeing).
If you ever figure out an easy way to work around this, do let me know; I'm very interested.