NOTE: This is mentioned in the question but restarting Visual Studio fixes the issue in most cases.
Updating Visual Studio to 'Update 2' got it working again.
Tools -> Extensions and Updates ->Visual Studio Update 2
As mentioned in the question and the link i posted therein, I'd already updated NuGet Package Manager to 3.4.4 prior to this and restarted to no avail, so I don't know if the combination of both these actions worked.