Yea, it worked, don't know what I did wrong before but I followed your instructions exactly and it worked first time
Chances are you did nothing wrong before.
From the pattern I'm seeing from the upgrades, it's sounding like Google may be using an availability algorithm with some form of gating internal to the device. In other words, when you request the upgrade, if a slot happens to be open on a server at that moment you get the upgrade. If you fail to get it, to save overloading from people mashing the upgrade check button every 2 seconds for an hour, the device is taken out of the round for a certain amount of time - I'd be willing to bet the "check for updates" button acts as a placebo 90% of the time and is programmed to do an actual check every hour or two at most.
Clearing the Google Services Framework makes your device think you haven't checked for a long time, and your device then actually checks the server - and if a slot happens to be available at that moment, you're in.
So if my wild-ass guess is correct, clearing the Framework simply allows you to perform the check for real more often, increasing your chances of getting a "hit" on an open slot on the upgrade server. So, in your case, it's probably that you successfully cleared the framework, but your attempt to connect was met with an "all servers busy" and your device went back into placebo mode. This time, your reset resulted in a connection during a split second when a server slot was available, and you're in.
Over the course of the next few days or so, the number of devices that are asking for the upgrade will dwindle (as they've already been upgraded) and your chances of getting the upgrade will increase.